Average-case complexity and decision problems in group theory.
From MaRDI portal
word problemdecision problemsfinitely presented groupsmembership problemaverage-case complexitygeneric-case complexity
Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Topological methods in group theory (57M07) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity of computation (including implicit computational complexity) (03D15)
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
- 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?)
- 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)
- Lectures on hyperbolic geometry
- On spectra of simple random walks on one-relator groups. With an appendix by Paul Jolissaint
- Random Walks on Infinite Graphs and Groups - a Survey on Selected topics
- Random walk in random groups.
- 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-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
- Word Problems Solvable in Logspace
Cited in
(37)- Randomness and complexity in matrix groups
- Generic amplification of recursively enumerable sets
- Random equations in nilpotent groups.
- Combinatorial group theory and public key cryptography
- Diophantine cryptography over infinite groups
- Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
- Algorithmically finite groups.
- On generic complexity of the validity problem for Boolean formulas
- Improved parallel algorithms for generalized Baumslag groups
- On mathematical contributions of Paul E. Schupp
- Generic complexity of Presburger arithmetic
- A generic relation on recursively enumerable sets
- The subadditive ergodic theorem and generic stretching factors for free group automorphisms.
- GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS
- Tracking rates of random walks
- Exponentially generic subsets of groups
- Average-case complexity of the Whitehead problem for free groups
- On generic complexity of the discrete logarithm problem
- The central tree property and algorithmic problems on subgroups of free groups
- Generic case completeness
- APPROXIMATION OF GEODESICS IN METABELIAN GROUPS
- ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM
- ON GENERIC COMPLEXITY OF THE PROBLEM OF FINDING ROOTS IN GROUPS OF RESIDUES
- On the strongly generic undecidability of the halting problem
- RANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUP
- Some geodesic problems in groups
- Random equations in free groups.
- Expander graphs in pure and applied mathematics
- Random quotients of the modular group are rigid and essentially incompressible
- Partial word and equality problems and Banach densities
- Genericity of filling elements.
- Random van Kampen diagrams and algorithmic problems in groups.
- Some metric properties of automorphisms of groups.
- Generic-case complexity, decision problems in group theory, and random walks.
- Search and witness problems in group theory.
- Generic complexity of undecidable problems
- Generic undecidability of universal theories
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)
