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 $\leq^{p}_{m}$‐hard for NP. We demonstrate the existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$ such that for every $L \in \mbox{NP} - \mbox{P}$, L - S is not $\leq^p_m$‐hard for NP. Moreover, we prove for every $L \in \mbox{NP} - \mbox{P}$ that there exists a sparse $S \in $ EXP such that L - S is not $\leq^p_m$‐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 quasi‐polynomial‐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 the 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 \co\UP$ contains DTIME$(2^{n^{\epsilon}})$‐bi‐immune sets, then this hypothesis is true.

We study several properties of sets that are complete for NP. We prove that if L is an NP-complete set and S /spl nsupe/ L is a p-selective sparse set, then L -S is /spl les//sub m//sup p/-hard for NP. We demonstrate existence of a sparse set S /spl isin/ DTIME(2/sup 2n/) such that for every L /spl isin/ NP - P, L - S is not /spl les//sub m//sup p/-hard for NP. Moreover, we prove for every L /spl isin/ NP - P, that there exists a sparse S /spl isin/ EXP such that L - S is not /spl les//sub m//sup p/-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 long-standing 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/sup ne/)-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 < /spl epsi/ < 1, no 2/sup ne/ time-bounded machine can correctly compute infinitely many accepting computations of M, We show that if UP /spl cap/ coUP contains DTIME(2/sup ne/)-bi-immune sets, then this hypothesis is true.

Razborov (1994) proved that existence of an optimal proof system implies existence of a many-one complete disjoint NP-pair. Kobler, Messner, and Toran (2003) defined a stronger form of many-one reduction and claimed to improve Razborov's result by showing under the same assumption that there is a strongly many-one complete disjoint NP-pair. Here we show that the two results are equivalent. More generally, we prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A, B, C, and D be nonempty sets belonging to NP. A smart reduction between the disjoint NP-pairs (A,B) and (C,D) is a Turing reduction with the additional property that if the input belongs to A /spl cup/ B, then all queries belong to C /spl cup/ D. We prove under the reasonable assumption UP /spl cap/ co-UP has a P-bi-immune set that there exist disjoint NP-pairs (A,B) and (C,D) such that (A,B) is truth-table reducible to (C,D), but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DisjNP has a truth-table-complete disjoint NP-pair, but has no many-one- complete disjoint NP-pair.

It is known (Boppana et a;., 1987) that if every language in coNP has a constant-round interactive proof system, then the polynomial hierarchy collapses. On the other hand, Lund et al. (1992) have shown that #SAT, the #P-complete function that outputs the number of satisfying assignments of a Boolean formula, can be computed by a linear-round interactive protocol. As a consequence, the coNP-complete set SAT has a proof system with linear rounds of interaction. We show that if every set in coNP has a polylogarithmic-round interactive protocol then the exponential hierarchy collapses to the third level. In order to prove this, we obtain an exponential version of Yap's result (1983), and improve upon an exponential version of the Karp-Lipton theorem (1980), obtained first by Buhrman and Homer (1992).

We study the question of whether the class DisjNP of disjoint pairs (A, B) of NP-sets contains a complete pair. The question relates to the question of whether optimal proof systems exist, and we relate it to the previously studied question of whether there exists a disjoint pair of NP-sets that is NP-hard. We show under reasonable hypotheses that nonsymmetric disjoint NP-pairs exist, which provides additional evidence for the existence of P-inseparable disjoint NP-pairs. We construct an oracle relative to which the class of disjoint NP-pairs does not have a complete pair; an oracle relative to which optimal proof systems exist, and hence complete pairs exist, but no pair is NP-hard; and an oracle relative to which complete pairs exist, but optimal proof systems do not exist.

We show that if SAT does not have small circuits, then there must exist a small number of formulas such that every small circuit fails to compute satisfiability correctly on at least one of these formulas. We use this result to show that if P/sup NP[1]/=P/sup NP[2]/, then the polynomial-time hierarchy collapses to S/sub 2//sup P//spl sube//spl Sigma//sub 2//sup p//spl cap//spl Pi//sub 2//sup p/. Even showing that the hierarchy collapsed to /spl Sigma//sub 2//sup p/ remained open.

We study the question of whether the class DisNP of disjoint pairs (A, B) of NP-sets contains a complete pair. The question relates to the question of whether optimal proof systems exist, and we relate it to the previously studied question of whether there exists a disjoint pair of NP-sets that is NP-hard. We show under reasonable hypotheses that nonsymmetric disjoint NP-pairs exist, which provide additional evidence for the existence of P-inseparable disjoint NP-pairs. We construct an oracle relative to which the class of disjoint NP-pairs does not have a complete pair, an oracle relative to which optimal proof systems exist, hence complete pairs exist, but no pair is NP-hard, and an oracle relative to which complete pairs exist, but optimal proof systems do not exist.