Average-case complexity and decision problems in group theory.
From MaRDI portal
average-case complexitydecision problemsfinitely presented groupsgeneric-case complexitymembership problemword problem
Complexity of computation (including implicit computational complexity) (03D15) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Topological methods in group theory (57M07) Analysis of algorithms and problem complexity (68Q25)
Abstract: We investigate the average-case complexity of decision problems for finitely generated groups, in particular the word and membership problems. Using our recent results on ``generic-case complexity we show that if a finitely generated group has the word problem solvable in subexponential time and has a subgroup of finite index which possesses a non-elementary word-hyperbolic quotient group, then the average-case complexity of the word problem for is linear time, uniformly with respect to the collection of all length-invariant measures on . For example, the result applies to all braid groups .
Recommendations
Cites work
- A finiteness property and an automatic structure for Coxeter groups
- A property of subgroups of infinite index in a free group
- A small simplification in hyperbolic groups
- ALMOST EVERY GROUP IS HYPERBOLIC
- Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces
- An asymptotic Freiheitssatz for finitely generated groups
- Artin groups and infinite Coxeter groups
- Artin groups of extra-large type are biautomatic
- Automatic groups and amalgams
- Automatic groups: A guided tour
- Average Case Complete Problems
- Cogrowth and amenability of discrete groups
- Cogrowth of groups and simple random walks
- Counting paths in graphs
- Critical densities for random quotients of hyperbolic groups.
- Distributional Word Problem for Groups
- Dynamic theory of growth in groups: Entropy, boundaries, examples
- Generic properties of finitely presented groups and howson's theorem
- Generic-case complexity, decision problems in group theory, and random walks.
- Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
- Groups with two More Generators Than Relators
- Géométrie et théorie des groupes. Les groupes hyperboliques de Gromov. (Geometry and group theory. The hyperbolic groups of Gromov)
- scientific article; zbMATH DE number 988812 (Why is no real title available?)
- scientific article; zbMATH DE number 437296 (Why is no real title available?)
- scientific article; zbMATH DE number 4031953 (Why is no real title available?)
- scientific article; zbMATH DE number 3661276 (Why is no real title available?)
- scientific article; zbMATH DE number 53661 (Why is no real title available?)
- scientific article; zbMATH DE number 67424 (Why is no real title available?)
- scientific article; zbMATH DE number 3574107 (Why is no real title available?)
- scientific article; zbMATH DE number 1263208 (Why is no real title available?)
- scientific article; zbMATH DE number 1320672 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1004927 (Why is no real title available?)
- scientific article; zbMATH DE number 1072538 (Why is no real title available?)
- scientific article; zbMATH DE number 1535398 (Why is no real title available?)
- scientific article; zbMATH DE number 1795121 (Why is no real title available?)
- scientific article; zbMATH DE number 1836314 (Why is no real title available?)
- scientific article; zbMATH DE number 849252 (Why is no real title available?)
- Lectures on hyperbolic geometry
- On spectra of simple random walks on one-relator groups. With an appendix by Paul Jolissaint
- Random walk in random groups.
- Random Walks on Infinite Graphs and Groups - a Survey on Selected topics
- Rational subgroups of biautomatic groups
- Statistical properties of finitely presented groups
- Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
- The class of groups all of whose subgroups with lesser number of generators are free is generic
- The complexity of Dehn's algorithm for word problems in groups
- The nonamenability of Schreier graphs for infinite index quasiconvex subgroups of hyperbolic groups.
- The space of finitely generated groups
- Word Problems Solvable in Logspace
- WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
Cited in
(43)- Generic-case complexity, decision problems in group theory, and random walks.
- Generic amplification of recursively enumerable sets
- Tracking rates of random walks
- Partial word and equality problems and Banach densities
- Generic undecidability of universal theories
- A generic relation on recursively enumerable sets
- Combinatorial group theory and public key cryptography
- Random van Kampen diagrams and algorithmic problems in groups.
- Random equations in free groups.
- Some geodesic problems in groups
- Search and witness problems in group theory.
- Expander graphs in pure and applied mathematics
- Generic complexity of undecidable problems
- RANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUP
- Random quotients of the modular group are rigid and essentially incompressible
- scientific article; zbMATH DE number 1263208 (Why is no real title available?)
- Distributional Word Problem for Groups
- Random equations in nilpotent groups.
- Diophantine cryptography over infinite groups
- 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
- GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS
- Genericity of filling elements.
- APPROXIMATION OF GEODESICS IN METABELIAN GROUPS
- Average-case complexity of the Whitehead problem for free groups
- Improved parallel algorithms for generalized Baumslag groups
- Algorithmically finite groups.
- The central tree property and algorithmic problems on subgroups of free groups
- Orbit-blocking words in free groups
- Linear average-case complexity of algorithmic problems in groups
- Orbit-blocking words and the average-case complexity of Whitehead's problem in the free group of rank 2
- Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
- On mathematical contributions of Paul E. Schupp
- Exponentially generic subsets of groups
- Automorphic orbits in free groups: recent progress
- Generic case completeness
- Randomness and complexity in matrix groups
- Generic complexity of Presburger arithmetic
- Some metric properties of automorphisms of groups.
- The subadditive ergodic theorem and generic stretching factors for free group automorphisms.
- On the strongly generic undecidability of the halting problem
This page was built for publication: Average-case complexity and decision problems in group theory.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703812)
