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 (only showing first 100 items - show all)

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

This page was built for publication: Generic-case complexity, decision problems in group theory, and random walks.