Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis
Mandal, Debasis, A. Pavan, Rajeswari Venugopalan · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2014
We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a worst-case hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time O(2^2^n^c) (for some c > 1) accepting Sigma^* whose accepting computations cannot be computed by bounded-error, probabilistic machines running in time O(2^2^{beta * 2^n^c) (for some beta > 0). This is the first result that separates completeness notions for NP under a worst-case hardness hypothesis.