TR04-019 Authors: Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta

Publication: 18th March 2004 22:06

Downloads: 1450

Keywords:

We study several properties of sets that are complete for NP.

We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$

such that for every $L \in NP - P$, $L - S$ is not many-one-hard for NP.

Moreover, we prove for every $L \in NP - P$, that there exists a

sparse $S \in EXP$ such that $L - S$ is not many-one-hard for NP.

Hence, removing sparse information in P from a complete set leaves the

set complete, while removing sparse information in EXP from a complete

set may destroy its completeness. Previously, these properties were known only for exponential time complexity classes.

We use hypotheses about pseudorandom generators and secure one-way permutations to resolve longstanding open questions about whether NP-complete sets are immune. For example, assuming that pseudorandom generators and secure one-way permutations exist,

it follows easily that NP-complete sets are not p-immune.

Assuming only that secure one-way permutations exist, we prove that

no NP-complete set is $DTIME(2^{n^\epsilon})$-immune. Also, using these

hypotheses we show that no NP-complete set is quasipolynomial-close to P.

We introduce a strong but reasonable hypothesis and infer from it that

disjoint Turing-complete sets for NP are not closed under union. Our hypothesis

asserts existence of a UP-machine $M$ that accepts $0^*$ such

that for some $0 < \epsilon < 1$, no $2^{n^{\epsilon}}$ time-bounded

machine can correctly compute infinitely many accepting

computations of $M$. We show that if

$UP \cap coUP$ contains $DTIME(2^{n^{\epsilon}})$-bi-immune sets, then

this hypothesis is true.