Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis
From MaRDI portal
Publication:2978535
DOI10.4230/LIPIcs.FSTTCS.2014.445zbMath1360.68482MaRDI 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/
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)