Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis

DOI10.4230/LIPICS.FSTTCS.2014.445zbMath1360.68482OpenAlexW2246416211MaRDI QIDQ2978535

Rajeswari Venugopalan, Debasis Mandal, A. Pavan

Publication date: 25 April 2017

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2014/4862/

zbMATH Keywords

NP-completenessTuring completenessCook reductionmany-one completenessKarp reduction

Mathematics Subject Classification ID

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

This page was built for publication: Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis