Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > KARP REDUCTION:
Reports tagged with Karp Reduction:
TR14-126 | 9th October 2014
Debasis Mandal, A. Pavan, Rajeswari Venugopalan

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

We 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 ... more >>>




ISSN 1433-8092 | Imprint