Generic-case complexity, decision problems in group theory, and random walks.

DOI10.1016/S0021-8693(03)00167-4zbMath1041.20021arXivmath/0203239MaRDI QIDQ1399190

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

Publication date: 30 July 2003

Published in: Journal of Algebra (Search for Journal in Brave)

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

zbMATH Keywords

finitely generated groupsword problemmembership problemrandom walks on graphsconjugacy problemgeneric-case complexitydecision problems in group theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Subgroup theorems; subgroup growth (20E07) Generators, relations, and presentations of groups (20F05) Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Average-case complexity of the Whitehead problem for free groups, Parallel algorithms for power circuits and the word problem of the Baumslag group, Generic complexity of the word problem in some semigroups, Generically Computable abelian groups, Improved parallel algorithms for generalized Baumslag groups, Post's correspondence problem: from computer science to algebra, Unnamed Item, 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, Variations on the post correspondence problem for free groups, Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem, Asymptotic density, computable traceability, and 1-randomness, Nonexistence of minimal pairs for generic computability, Generic complexity of Presburger arithmetic, Generically and coarsely computable isomorphisms, Generic complexity of the membership problem for semigroups of integer matrices, Computability theory. Abstracts from the workshop held February 5--11, 2012., Asymptotic density, immunity and randomness, On the generic undecidability of the halting problem for normalized Turing machines, On probabilistic algorithm for solving almost all instances of the set partition problem, Følner functions and the generic word problem for finitely generated amenable groups, Primitivity rank for random elements in free groups, Generic Kleene fixed point theorem, The subadditive ergodic theorem and generic stretching factors for free group automorphisms., Generic hardness of the Boolean satisfiability problem, THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY, Partial word and equality problems and Banach densities, On the strongly generic undecidability of the halting problem, Counting problems in graph products and relatively hyperbolic groups, THE CONJUGACY PROBLEM IN AMALGAMATED PRODUCTS I: REGULAR ELEMENTS AND BLACK HOLES, Finitely presented expansions of computably enumerable semigroups, Generic complexity of undecidable problems, A MINIMAL PAIR IN THE GENERIC DEGREES, DENSITY-1-BOUNDING AND QUASIMINIMALITY IN THE GENERIC DEGREES, Affine braid groups: a better platform than braid groups for cryptology?, Combinatorial group theory and public key cryptography, One-relator quotients of right-angled Artin groups, Random equations in nilpotent groups., RANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUP, Asymptotic Density and the Theory of Computability: A Partial Survey, Compressed word problems in HNN-extensions and amalgamated products, Some Questions in Computable Mathematics, Algorithmically finite groups., Generic properties of subgroups of free groups and finite presentations, COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS, Generic complexity of finitely presented monoids and semigroups, 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 group-theoretic models of randomness and genericity., 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 NP-COMPLETENESS OF THE BOOLEAN SATISFIABILITY PROBLEM, ON GENERIC COMPLEXITY OF DECIDABILITY PROBLEM FOR DIOPHANTINE SYSTEMS IN THE SKOLEM’S FORM, ON GENERIC COMPLEXITY OF THE PROBLEM OF FINDING ROOTS IN GROUPS OF RESIDUES, RELATIVIZED GENERIC CLASSES P AND NP, ON GENERIC UNDECIDABILITY OF HILBERT’S TENTH PROBLEM FOR POLYNOMIAL TREES, ON BINARY SOLUTIONS TO SYSTEMS OF EQUATIONS, ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM, ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY, ON GENERIC COMPLEXITY OF THE PROBLEM OF REPRESENTATION OF NATURAL NUMBERS BY SUM OF TWO SQUARES, ON GENERIC COMPLEXITY OF THE EXISTENTIAL THEORIES, ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS, Finitely presented expansions of groups, semigroups, and algebras, COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS, EFFICIENT ALGORITHMS FOR HIGHLY COMPRESSED DATA: THE WORD PROBLEM IN HIGMAN'S GROUP IS IN P, INTRINSIC SMALLNESS, On two-generator subgroups in \(\mathrm{SL}_2(\mathbb{Z})\), \(\mathrm{SL}_2(\mathbb{Q})\), and \(\mathrm{SL}_2(\mathbb{R})\), Generic Gödel's incompleteness theorem, Statistical properties of subgroups of free groups, Average-case complexity and decision problems in group theory., Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups., On mathematical contributions of Paul E. Schupp, Sublinear time algorithms in the theory of groups and semigroups., Exponentially generic subsets of groups, Algorithmic search in group theory, THE GENERIC DEGREES OF DENSITY-1 SETS, AND A CHARACTERIZATION OF THE HYPERARITHMETIC REALS, Conjugacy in Baumslag's group, generic case complexity, and division in power circuits, Asymptotic density and the coarse computability bound, Large groups of deficiency 1., Generic Case Complexity and One-Way Functions, Using Decision Problems in Public Key Cryptography, Generic case completeness, Random quotients of the modular group are rigid and essentially incompressible, Solving the Conjugacy Decision Problem via Machine Learning, The conjugacy problem for Higman’s group, Search and witness problems in group theory, Compressed Word Problems in HNN-Extensions and Amalgamated Products, Asymptotic density and computability, Computable permutations and word problems, Average complexity of Moore's and Hopcroft's algorithms, Minimisation of automata, Negligibity of elliptic elements in ascending HNN-extensions of Zm, A GATHERING PROCESS IN ARTIN BRAID GROUPS, Expander graphs in pure and applied mathematics, An attack on the Walnut digital signature algorithm, Unnamed Item, Unnamed Item, Generic undecidability of universal theories, Search problems in groups and branching processes, The generic complexity of the bounded problem of graphs clustering, The generic complexity of the graph triangulation problem, An average study of hypergraphs and their minimal transversals, Compression techniques in group theory

Uses Software

• MAGNUS

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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast method for comparing braids
• Artin groups and infinite Coxeter groups
• Cogrowth of groups and simple random walks
• Cogrowth and amenability of discrete groups
• Average case completeness
• 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)
• A new approach to the word and conjugacy problems in the braid groups
• Cesàro's theorems for complex sequences
• A small simplification in hyperbolic groups
• The class of groups all of whose subgroups with lesser number of generators are free is generic
• The nonamenability of Schreier graphs for infinite index quasiconvex subgroups of hyperbolic groups.
• The space of finitely generated groups
• An algebraic method for public-key cryptography
• 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
• Coxeter groups, 2-completion, perimeter reduction and subgroup separability.
• Statistical properties of finitely presented groups
• Free subgroups in linear groups
• Dynamic theory of growth in groups: Entropy, boundaries, examples
• SOLVING THE WORD PROBLEM IN REAL TIME
• 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
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• MULTIPLICATIVE MEASURES ON FREE GROUPS
• 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