Generic case completeness
From MaRDI portal
Publication:736607
DOI10.1016/J.JCSS.2016.05.002zbMATH Open1349.68099arXiv1606.01172OpenAlexW2963826388MaRDI QIDQ736607FDOQ736607
Alexei Myasnikov, Alexander Ushakov
Publication date: 4 August 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Abstract: In this note we introduce a notion of a generically (strongly generically) NP-complete problem and show that the randomized bounded version of the halting problem is strongly generically NP-complete.
Full work available at URL: https://arxiv.org/abs/1606.01172
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Statistical properties of finitely presented groups
- Generic complexity of undecidable problems
- ALMOST EVERY GROUP IS HYPERBOLIC
- Random walk in random groups.
- Title not available (Why is that?)
- Generic-case complexity, decision problems in group theory, and random walks.
- Generic computability, Turing degrees, and asymptotic density
- ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
- Average case completeness
- Average Case Complete Problems
- Generic properties of finitely presented groups and howson's theorem
- MULTIPLICATIVE MEASURES ON FREE GROUPS
- Average-case complexity and decision problems in group theory.
- Small fast universal Turing machines
- Title not available (Why is that?)
- The halting problem is decidable on a set of asymptotic probability one
- Asymptotic density and the Ershov hierarchy
- Nonexistence of minimal pairs for generic computability
- From Bi-Immunity to Absolute Undecidability
Cited In (1)
This page was built for publication: Generic case completeness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q736607)
