ContactPerson: selman@cse.buffalo.edu Remote host: selman.cse.buffalo.edu ### Begin Citation ### Do not delete this line ### %R 2004-03 %U /web/faculty/selman/properties.ps %A Glasser, Christian %A Pavan, A. %A Selman, Alan %A Sengupta, Samik %T Properties of NP-Complete Sets %D January 15, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K clossness, immunity, pseudorandom generators, secure one-way permutations, disjoint NP-pairs %X 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 $\redm$-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.