2 papers
math.GR1998
Isoperimetric Functions of Groups and Computational Complexity of the Word Problem
J. -C. Birget, A. Yu. Olshanskii, E. Rips +1
We prove that the word problem of a finitely generated group is in NP (solvable in polynomial time by a non-deterministic Turing machine) if and only if this group is a subgrou…
math.GR1998
Isoperimetric and isodiametric functions of groups
Mark Sapir, Jean-Camille Birget, Eliyahu Rips
This is the first of two papers devoted to connections between asymptotic functions of groups and computational complexity. One of the main results of this paper states that if for…