FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
From MaRDI portal
Publication:3520362
circuitscomplexitycoNP-completenessinfinite generating setslength preserving elementsThompson-Higman groupsword problem
Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Abstract: We consider the subgroup lpG_{k,1} of length preserving elements of the Thompson-Higman group G_{k,1} and we show that all elements of G_{k,1} have a unique lpG_{k,1}.F_{k,1} factorization. This applies to the Thompson-Higman group T_{k,1} as well. We show that lpG_{k,1} is a ``diagonal direct limit of finite symmetric groups, and that lpT_{k,1} is a k^infinity Pr"ufer group. We find an infinite generating set of lpG_{k,1} which is related to reversible boolean circuits. We further investigate connections between the Thompson-Higman groups, circuits, and complexity. We show that elements of F_{k,1} cannot be one-way functions. We show that describing an element of G_{k,1} by a generalized bijective circuit is equivalent to describing the element by a word over a certain infinite generating set of G_{k,1}; word length over these generators is equivalent to generalized bijective circuit size. We give some coNP-completeness results for G_{k,1} (e.g., the word problem when elements are given by circuits), and #P-completeness results (e.g., finding the lpG_{k,1}.F_{k,1} factorization of an element of G_{k,1} given by a circuit).
Recommendations
- The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
- CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
- Monoid generalizations of the Richard Thompson groups.
- The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
- THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
Cites work
- A construction which can be used to produce finitely presented infinite simple groups
- An infinite-dimensional torsion-free \(\text{FP}_{\infty}\) group
- CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
- Combinatorial properties of Thompson’s group 𝐹
- Conservative logic
- Geometric presentations for Thompson's groups.
- Groups of piecewise linear homeomorphisms of the real line
- 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 3409586 (Why is no real title available?)
- ON THE ZAPPA-SZÉP PRODUCT
- Parallel Prefix Computation
- Sur un groupe remarquable de difféomorphismes du cercle. (On a remarkable group of the diffeomorphisms of the circle)
- THE ALGEBRA OF STRAND SPLITTING II: A PRESENTATION FOR THE BRAID GROUP ON ONE STRAND
- The Chameleon groups of Richard J. Thompson: Automorphisms and dynamics
- THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
- The Ubiquity of Thompson's Group F in Groups of Piecewise Linear Homeomorphisms of the Unit Interval
Cited in
(7)- 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.
- The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
- CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
- Bernoulli measure on strings, and Thompson-Higman monoids.
- Monoid generalizations of the Richard Thompson groups.
- One-way permutations, computational asymmetry and distortion.
This page was built for publication: FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3520362)
