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

DOI10.1142/S0218196706002822zbMath1156.20309arXivmath/0310335OpenAlexW2091593086MaRDI QIDQ5470158

Jean-Camille 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

word problemfinitely presented groupscoNP-completenessThompson groups

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)

Related Items (13)

The co-word problem for the Higman-Thompson group is context-free ⋮ Automorphisms of shift spaces and the Higman--Thompson groups: the one-sided case ⋮ New embeddings between the Higman-Thompson groups ⋮ FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT 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. ⋮ One-way permutations, computational asymmetry and distortion. ⋮ THE ${\mathcal R}$- AND ${\mathcal L}$-ORDERS OF THE THOMPSON–HIGMAN MONOID M_{k, 1} AND THEIR COMPLEXITY ⋮ Infinitely generated semigroups and polynomial complexity ⋮ The word problem of the Brin-Thompson group is \textsf{coNP}-complete ⋮ Monoids that map onto the Thompson-Higman groups ⋮ Semigroups and one-way functions ⋮ Asymptotic invariants, complexity of groups and related problems

Cites Work

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

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