activity
19982003
most citedCircuits, coNP-completeness, and the groups of Richard Thompson

18 citations · 18 across the 2 of their papers we have counts for

collaborators
Showing 1998Show all

2 papers · 1 filter

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…