Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-005 | 3rd January 2002 00:00

Bi-Immunity Separates Strong NP-Completeness Notions

RSS-Feed




TR02-005
Authors: A. Pavan, Alan L. Selman
Publication: 9th January 2002 20:15
Downloads: 1953
Keywords: 


Abstract:

We prove that if for some epsilon > 0 NP contains a set that is
DTIME(2^{n^{epsilon}})-bi-immune, then NP contains a set that 2-Turing
complete for NP but not 1-truth-table complete for NP. Lutz and Mayordomo
(LM96) and Ambos-Spies and Bentzien (AB00) previously obtained the
same consequence using strong hypotheses involving resource-bounded
measure and.or category theory.



ISSN 1433-8092 | Imprint