Generic complexity of undecidable problems

DOI10.2178/jsl/1208359065zbMath1140.03025OpenAlexW2120230527MaRDI QIDQ3503760

Alexander N. Rybalov, Alexei G. Myasnikov

Publication date: 9 June 2008

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1208359065

zbMATH Keywords

word problemfinitely presented semigroupsRice theoremgeneric amplificationabsolutely undecidable problemsgeneric immune setsstrong undecidabilitysuper-undecidable problems

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35)

Related Items

Random equations in free groups ⋮ Generic case complexity of the graph isomorphism problem ⋮ Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem ⋮ Asymptotic density, computable traceability, and 1-randomness ⋮ Følner functions and the generic word problem for finitely generated amenable groups ⋮ Generic Kleene fixed point theorem ⋮ Partial word and equality problems and Banach densities ⋮ Generic complexity of the word problem in some semigroups ⋮ Asymptotic Density and the Theory of Computability: A Partial Survey ⋮ Algorithmically finite groups. ⋮ 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 ⋮ ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS ⋮ On mathematical contributions of Paul E. Schupp ⋮ Exponentially generic subsets of groups ⋮ Generic case completeness ⋮ Asymptotic density and computability ⋮ Expander graphs in pure and applied mathematics ⋮ Generic undecidability of universal theories ⋮ 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

Cites Work

• Average-case complexity and decision problems in group theory.
• On the strongly generic undecidability of the halting problem
• Generic-case complexity, decision problems in group theory, and random walks.
• The halting problem is decidable on a set of asymptotic probability one
• MULTIPLICATIVE MEASURES ON FREE GROUPS
• Recursive Unsolvability of a problem of Thue
• Unnamed Item