ECCC-Report TR14-126https://eccc.weizmann.ac.il/report/2014/126Comments and Revisions published for TR14-126en-usFri, 10 Oct 2014 12:45:13 +0300
Paper TR14-126
| Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis |
Debasis Mandal,
A. Pavan,
Rajeswari Venugopalan
https://eccc.weizmann.ac.il/report/2014/126We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a {\em 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.Fri, 10 Oct 2014 12:45:13 +0300https://eccc.weizmann.ac.il/report/2014/126