Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems

DOI10.4230/LIPICS.CCC.2020.29MaRDI QIDQ5092480zbMATH OpenFDO

Authors Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß

Publication date 21 July 2022

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

zbMATH Keywords

\(NC^1\)-hardnessG-programsGrigorchuk's groupnon-solvable groupsself-similar groupsstraight-line programsThompson's groupsword problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Space complexity and word problems of groups
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• The word and geodesic problems in free solvable groups.
• The word problem of the Brin-Thompson group is \textsf{coNP}-complete

Cites work

• A uniform approach to define complexity classes
• Arithmetic circuits: a survey of recent results and open questions
• Asymptotic aspects of Schreier graphs and Hanoi Towers groups.
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Compressed decision problems in hyperbolic groups
• Computational Complexity
• Counting classes: Thresholds, parity, mods, and fewness
• Coxeter groups are virtually special
• Embedding theorems for residually finite groups
• Evaluation of circuits over nilpotent and polycyclic groups
• Finite monoids and the fine structure of NC ¹
• Finite Monoids: From Word to Circuit Evaluation
• Free subgroups in linear groups
• Groups, languages and automata
• scientific article; zbMATH DE number 3642708 (Why is no real title available?)
• scientific article; zbMATH DE number 4145340 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• scientific article; zbMATH DE number 1088282 (Why is no real title available?)
• scientific article; zbMATH DE number 2156384 (Why is no real title available?)
• scientific article; zbMATH DE number 1453080 (Why is no real title available?)
• scientific article; zbMATH DE number 7650891 (Why is no real title available?)
• Introductory notes on Richard Thompson's groups
• Iterated monodromy groups of quadratic polynomials. I.
• Leaf languages and string compression
• Logspace and logtime leaf languages
• On balanced versus unbalanced computation trees
• On Burnside's problem on periodic groups
• On subgroups of R. Thompson's group F and other diagram groups
• On the Burnside problem for periodic groups
• Parallel identity testing for skew circuits with big powers and applications
• Querying and Embedding Compressed Texts
• Research announcement: The structure of groups with a quasiconvex hierarchy.
• Self-similar groups and their geometry
• The co-word problem for the Higman-Thompson group is context-free
• The complexity of Grigorchuk groups with application to cryptography
• The Compressed Word Problem for Groups
• The iterated mod problem
• The Ore conjecture.
• The Smallest Grammar Problem
• The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
• The word problem
• Word Problems Solvable in Logspace

Cited in

(7)

• Compression techniques in group theory
• An automaton group with \textsf{PSPACE}-complete word problem
• Parallel algorithms for power circuits and the word problem of the Baumslag group
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• The word problem for finitary automaton groups
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems

This page was built for publication: Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems

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