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.