CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS

DOI10.1142/S0218196706002822MaRDI QIDQ5470158zbMATH OpenOpenAlexFDO

Authors J.-C. Birget

Publication date 29 May 2006

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0310335

zbMATH Keywords

coNP-completenessfinitely presented groupsThompson groupsword problem

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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}.

Recommendations

• The word problem of the Brin-Thompson group is \textsf{coNP}-complete
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
• Monoid generalizations of the Richard Thompson groups.

Cites work

• A construction which can be used to produce finitely presented infinite simple groups
• A finitely presented simple group with unsolvable conjugacy problem
• Conservative logic
• Constructing finitely presented simple groups that contain Grigorchuk groups
• FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 47903 (Why is no real title available?)
• scientific article; zbMATH DE number 1033441 (Why is no real title available?)
• HYPERBOLICITY OF GROUPS WITH SUBQUADRATIC ISOPERIMETRIC INEQUALITY
• Isoperimetric and isodiametric functions of groups
• Isoperimetric functions of groups and computational complexity of the word problem
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• Logical Reversibility of Computation
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Reductions and functors from problems to word problems
• The complexity of Grigorchuk groups with application to cryptography
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
• Time/Space Trade-Offs for Reversible Computation
• Word Problems Solvable in Logspace

Cited in

(14)

• The word problem of the Brin-Thompson group is \textsf{coNP}-complete
• The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
• Asymptotic invariants, complexity of groups and related problems.
• Automorphisms of shift spaces and the Higman-Thompson groups: the one-sided case
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
• Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
• New embeddings between the Higman-Thompson groups
• Semigroups and one-way functions
• The co-word problem for the Higman-Thompson group is context-free
• Infinitely generated semigroups and polynomial complexity
• Monoids that map onto the Thompson-Higman groups
• Monoid generalizations of the Richard Thompson groups.
• One-way permutations, computational asymmetry and distortion.

This page was built for publication: CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470158)