ECCC-Report TR02-005https://eccc.weizmann.ac.il/report/2002/005Comments and Revisions published for TR02-005en-usWed, 09 Jan 2002 20:15:02 +0200
Paper TR02-005
| Bi-Immunity Separates Strong NP-Completeness Notions |
A. Pavan,
Alan L. Selman
https://eccc.weizmann.ac.il/report/2002/005We 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.
Wed, 09 Jan 2002 20:15:02 +0200https://eccc.weizmann.ac.il/report/2002/005