Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems

Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems We give lower bounds on the complexity of the word problem for a large class of non-solvable infinite groups that we call strongly efficiently non-solvable groups. This class includes free groups, Grigorchuk’s group, and Thompson’s groups. We prove that these groups have an NC1-hard word problem and that for some of them (including Grigorchuk’s group and Thompson’s groups) the compressed word problem (which is equivalent to the circuit evaluation problem) is PSPACE-complete. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems

Download PDF
41 pages

Loading next page...
 
/lp/association-for-computing-machinery/groups-with-alogtime-hard-word-problems-and-pspace-complete-compressed-00935mV8nr
Publisher
Association for Computing Machinery
Copyright
Copyright © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3569708
Publisher site
See Article on Publisher Site

Abstract

We give lower bounds on the complexity of the word problem for a large class of non-solvable infinite groups that we call strongly efficiently non-solvable groups. This class includes free groups, Grigorchuk’s group, and Thompson’s groups. We prove that these groups have an NC1-hard word problem and that for some of them (including Grigorchuk’s group and Thompson’s groups) the compressed word problem (which is equivalent to the circuit evaluation problem) is PSPACE-complete.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Feb 1, 2023

Keywords: NC1-hardness

References

  • Group laws and free subgroups in topological groups
    [,
  • The virtual Haken conjecture
    [,
  • Computational Complexity—A Modern Approach
    [,
  • Bounded-width polynomial-size branching programs recognize exactly those languages in \({NC}^1\)
    [,
  • Finite monoids and the fine structure of \(NC^{1}\)
    [,
  • Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
    [,
  • Branch groups
    [,
  • Iterated monodromy groups of quadratic polynomials
    [,
  • Finite Monoids: From word to circuit evaluation
    [,
  • Counting classes: Thresholds, parity, mods, and fewness
    [,
  • The word problem
    [,
  • A uniform approach to define complexity classes
    [,
  • Introductory notes on Richard Thompson’s groups
    [,
  • Nondeterministic NC \({}^{1}\) computation
    [,
  • The smallest grammar problem
    [,
  • Über unendliche diskontinuierliche Gruppen
    [,
  • The complexity of knapsack problems in wreath products
    [,
  • A universal tree balancing theorem
    [,
  • Computers and Intractability: A Guide to the Theory of NP-completeness
    [,
  • The complexity of Grigorchuk groups with application to cryptography
    [,
  • On Burnside’s problem on periodic groups
    [,
  • Asymptotic aspects of Schreier graphs and Hanoi Towers groups
    [,
  • On subgroups of the R
    [,
  • On the Burnside problem for periodic groups
    [,
  • Coxeter groups are virtually special
    [,
  • Relations among MOD-classes
    [,
  • Über Komplexitätsklassen, die mit Hilfe von k-wertigen Funktionen definiert werden
    [,
  • The shapes of trees
    [,
  • Algebraic acceptance mechanisms for polynomial time machines
    [,
  • On the power of polynomial time bit-reductions
    [,
  • On balanced versus unbalanced computation trees
    [,
  • A polynomial-time algorithm for deciding equivalence of normed context-free processes
    [,
  • The compressed word problem in relatively hyperbolic groups
    [,
  • Compressed decision problems in hyperbolic groups
    [,
  • Groups, Languages and Automata
    [,
  • Logspace and logtime leaf languages
    [,
  • The iterated mod problem
    [,
  • Evaluation of circuits over nilpotent and polycyclic groups
    [,
  • Parallel identity testing for skew circuits with big powers and applications
    [,
  • The co-word problem for the Higman-Thompson group is context-free
    [,
  • The Ore conjecture
    [,
  • Querying and embedding compressed texts
    [,
  • Word problems solvable in logspace
    [,
  • Word problems and membership problems on compressed words
    [,
  • Leaf languages and string compression
    [,
  • The Compressed Word Problem for Groups
    [,
  • Isomorphism of regular trees and words
    [,
  • The power word problem
    [,
  • Memory bounds for recognition of context-free and context-sensitive languages
    [,
  • Maintaining dynamic sequences under equality-tests in polylogarithmic time
    [,
  • Self-similar Groups
    [,
  • On the algorithmic unsolvability of the word problem in group theory
    [,
  • Testing equivalence of morphisms on context-free languages
    [,
  • Parallel Algorithms for Group Word Problems
    [,
  • An Introduction to the Theory of Groups (4th ed
    [,
  • Arithmetic circuits: A survey of recent results and open questions
    [,
  • Word problems for groups and contextfree recognition
    [,
  • Algebraic methods in the theory of lower bounds for Boolean circuit complexity
    [,
  • Free subgroups in linear groups
    [,
  • Introduction to Circuit Complexity
    [,
  • The parallel complexity of some constructions in combinatorial group theory
    [,
  • An automaton group with PSPACE-complete word problem
    [,
  • Embedding theorems for residually finite groups
    [,
  • Research announcement: The structure of groups with a quasiconvex hierarchy
    [,