Isoperimetric Functions of Groups and Computational Complexity of the Word Problem

1998/11/18 by Jean-Camille Birget, J. -C. Birget, Birget, J. -C. +8 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Geometric and Algebraic Topology #math.GR #msc:20 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/9811106

47 pages

arxiv created 1998/11/18 · arxiv updated 2009/11/30

Abstract

We prove that the word problem of a finitely generated group G is in NP (solvable in polynomial time by a non-deterministic Turing machine) if and only if this group is a subgroup of a finitely presented group H with polynomial isoperimetric function. The embedding can be chosen in such a way that G has bounded distortion in H.

Cited by

• HNN extensions and embedding theorems for groups

Related

• Functions on groups and computational complexity
• Quasi-isometric Higman embeddings and the Dehn function
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• A Finitely presented group whose word problem has sampleable hard instances
• The bounded and precise word problems for presentations of groups