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

2003/10/21 by Jean-Camille Birget, Birget, Jean-Camille
Computer Science · Mathematics · #20F10 #68Q15 #Coding theory and cryptography #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #math.GR #msc:20F10 #msc:68Q15 #semigroups and automata theory

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

73 pages

arxiv created 2003/10/21 · openalex publication_date 2003/10/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• The word problem of the Brin-Thompson group is coNP-complete
• The word problem of the Brin-Higman-Thompson groups
• The groups of Richard Thompson and complexity
• Factorizations of the Thompson-Higman groups, and circuit complexity
• Some properties of Higman-Thompson monoids and digital circuits