18 citations · 42 across the 30 of their papers we have counts for
Showing 1998Show all
2 papers · 1 filter
math.GR1998★ 2 cited
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★ 3 cited
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…