Generic case completeness

DOI10.1016/J.JCSS.2016.05.002zbMath1349.68099arXiv1606.01172OpenAlexW2963826388MaRDI 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

completenessgeneric-case complexitybounded halting problemrandomized problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY

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

This page was built for publication: Generic case completeness