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.