Generic case completeness

DOI10.1016/j.jcss.2016.05.002zbMath1349.68099arXiv1606.01172MaRDI QIDQ736607

Alexander Ushakov, Alexei G. Myasnikov

Publication date: 4 August 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

completeness; generic-case complexity; bounded halting problem; randomized problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Average-case complexity and decision problems in group theory.
• Average case completeness
• Generic-case complexity, decision problems in group theory, and random walks.
• Random walk in random groups.
• Statistical properties of finitely presented groups
• The halting problem is decidable on a set of asymptotic probability one
• Small fast universal Turing machines
• Generic computability, Turing degrees, and asymptotic density
• Generic complexity of undecidable problems
• Average Case Complete Problems
• ALMOST EVERY GROUP IS HYPERBOLIC
• Generic properties of finitely presented groups and howson's theorem
• MULTIPLICATIVE MEASURES ON FREE GROUPS
• Asymptotic density and the Ershov hierarchy
• Nonexistence of minimal pairs for generic computability
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• From Bi-Immunity to Absolute Undecidability