All natural NP-complete problems have average-case complete versions
From MaRDI portal
Publication:626691
DOI10.1007/S00037-010-0298-9zbMATH Open1213.68315OpenAlexW2037022371MaRDI QIDQ626691
Publication date: 18 February 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-010-0298-9
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
A Natural NP-Complete Problem with a Nontrivial Lower Bound ⋮ All NP-Problems Can Be Solved in Polynomial Time by Accepting Networks of Splicing Processors of Constant Size ⋮ On the average-case complexity of parameterized clique
This page was built for publication: All natural NP-complete problems have average-case complete versions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626691)
