Properties of NP-complete sets

Abstract

We study several properties of sets that are complete for NP. We prove that if L is an NP-complete set and S is a p-selective sparse set, then L - S is many-one hard for NP. We demonstrate existence of a sparse set S in $DTIME(2$ ^2ⁿ) 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 derive consequences for 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 &le &epsilon &le 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.

SIAM Journal on Computing, to appear.
Proceedings of the 19th IEEE Conference on Computational Complexity, 2004. 184-197 .