Circuits, coNP-completeness, and the groups of Richard Thompson

Abstract

We construct a finitely presented group with coNP-complete word problem, and a finitely generated simple group with coNP-complete word problem. These groups are represented as Thompson groups, hence as partial transformation groups of strings. The proof provides a simulation of combinational circuits by elements of the Thompson-Higman group G_{3,1}.

73 pages

Cited by in corpus (7)

• Monoids that map onto the Thompson-Higman groups
• New embeddings between the Higman-Thompson groups
• A monoid version of the Brin-Higman-Thompson groups
• Evaluation problems for the Thompson group and the Brin-Thompson group, and their relation to the word problem
• The word problem of the Brin-Thompson group is coNP-complete
• Infinitely generated semigroups and polynomial complexity
• Monoid generalizations of the Richard Thompson groups