Average-case complexity and decision problems in group theory.

DOI10.1016/j.aim.2003.02.001zbMath1065.20044arXivmath/0206273OpenAlexW2104285308MaRDI QIDQ703812

Ilya Kapovich, Vladimir Shpilrain, Alexei G. Myasnikov, Paul E. Schupp

Publication date: 11 January 2005

Published in: Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

decision problemsword problemfinitely presented groupsmembership problemaverage-case complexitygeneric-case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Topological methods in group theory (57M07) Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

Average-case complexity of the Whitehead problem for free groups, Random van Kampen diagrams and algorithmic problems in groups, Randomness and complexity in matrix groups, Random equations in free groups, A generic relation on recursively enumerable sets, Generic complexity of Presburger arithmetic, Some metric properties of automorphisms of groups., The subadditive ergodic theorem and generic stretching factors for free group automorphisms., Partial word and equality problems and Banach densities, On the strongly generic undecidability of the halting problem, Generic complexity of undecidable problems, Improved parallel algorithms for generalized Baumslag groups, Combinatorial group theory and public key cryptography, Random equations in nilpotent groups., RANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUP, Algorithmically finite groups., GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS, GENERICITY OF FILLING ELEMENTS, Generic amplification of recursively enumerable sets, ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM, ON GENERIC COMPLEXITY OF THE VALIDITY PROBLEM FOR BOOLEAN FORMULAS, ON GENERIC COMPLEXITY OF THE DISCRETE LOGARITHM PROBLEM, ON GENERIC COMPLEXITY OF THE PROBLEM OF FINDING ROOTS IN GROUPS OF RESIDUES, Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups., Tracking rates of random walks, On mathematical contributions of Paul E. Schupp, Exponentially generic subsets of groups, Conjugacy in Baumslag's group, generic case complexity, and division in power circuits, Generic case completeness, Random quotients of the modular group are rigid and essentially incompressible, Search and witness problems in group theory, Expander graphs in pure and applied mathematics, Unnamed Item, Generic undecidability of universal theories

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
• Artin groups and infinite Coxeter groups
• Cogrowth of groups and simple random walks
• Cogrowth and amenability of discrete groups
• Rational subgroups of biautomatic groups
• Automatic groups and amalgams
• Géométrie et théorie des groupes. Les groupes hyperboliques de Gromov. (Geometry and group theory. The hyperbolic groups of Gromov)
• Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
• Lectures on hyperbolic geometry
• A finiteness property and an automatic structure for Coxeter groups
• A small simplification in hyperbolic groups
• The class of groups all of whose subgroups with lesser number of generators are free is generic
• Generic-case complexity, decision problems in group theory, and random walks.
• Random walk in random groups.
• Critical densities for random quotients of hyperbolic groups.
• The nonamenability of Schreier graphs for infinite index quasiconvex subgroups of hyperbolic groups.
• The space of finitely generated groups
• An asymptotic Freiheitssatz for finitely generated groups
• Counting paths in graphs
• Automatic groups: A guided tour
• On spectra of simple random walks on one-relator groups. With an appendix by Paul Jolissaint
• Statistical properties of finitely presented groups
• Artin groups of extra-large type are biautomatic
• Dynamic theory of growth in groups: Entropy, boundaries, examples
• Average Case Complete Problems
• The complexity of Dehn's algorithm for word problems in groups
• ALMOST EVERY GROUP IS HYPERBOLIC
• Word Problems Solvable in Logspace
• Groups with two More Generators Than Relators
• Generic properties of finitely presented groups and howson's theorem
• Distributional Word Problem for Groups
• Random Walks on Infinite Graphs and Groups - a Survey on Selected topics
• A property of subgroups of infinite index in a free group
• Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM