We investigate autoreducibility properties of complete sets for NEXP under different polynomial-time reductions. Specifically, we show that under some polynomial-time reductions there are complete sets for NEXP that are not autoreducible. We show that settling the question whether every complete set for NEXP under non-adaptative reduction is autoreducible under NOR-truth-table reduction either positively or negatively would lead to major results about the exponential time complexity classes.

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long-standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glaßer et al., complete sets for all of the following complexity classes are m-mitotic: $\mathrm{NP}$, $\mathrm{coNP}$, $\oplus\mathrm{P}$, $\mathrm{PSPACE}$, and $\mathrm{NEXP}$, as well as all levels of $\mathrm{PH}$, $\mathrm{MODPH}$, and the Boolean hierarchy over $\mathrm{NP}$. In the cases of $\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NEXP}$, and $\mathrm{PH}$, this at once answers several well-studied open questions. These results tell us that complete sets share a redundancy that was not known before. In particular, every $\mathrm{NP}$-complete set A splits into two $\mathrm{NP}$-complete sets $A_1$ and $A_2$. We disprove the equivalence between autoreducibility and mitoticity for all polynomial-time-bounded reducibilities between 3-tt-reducibility and Turing-reducibility: There exists a sparse set in $\mathrm{EXP}$ that is polynomial-time 3-tt-autoreducible, but not weakly polynomial-time T-mitotic. In particular, polynomial-time T-autoreducibility does not imply polynomial-time weak T-mitoticity, which solves an open question by Buhrman and Torenvliet.

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 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.

We use hypotheses of structural complexity theory to separate various NP-completeness notions. In particular, we introduce a hypothesis from which we describe a set in NP that is /spl les//sub T//sup P/-complete but not /spl les//sub tt//sup P/-complete. We provide fairly thorough analyses of the hypotheses that we introduce.

We use hypotheses of structural complexity theory to separate various NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is $\mbox{${\leq}^{\rm P}_{\rm T}$}$-complete but not $\mbox{${\leq}^{\rm P}_{tt}$}$-complete. We provide fairly thorough analyses of the hypotheses that we introduce.

We extend Levin's definition of average polynomial time to arbitrary time-bounds in accordance with the following general principles: (1) It essentially agrees with Levin's notion when applied to polynomial time-bounds. (2) If a language L belongs to DTIME(T(n)) for some time-bound T(n), then every distributional problem $(L,\mu)$ is T on the $\mu$-average. (3) If L does not belong to DTIME(T(n)) almost everywhere, then no distributional problem $(L,\mu)$ is T on the $\mu$-average. We present hierarchy theorems for average-case complexity, for arbitrary time-bounds, that are as tight as the well-known Hartmanis--Stearns hierarchy theorem for deterministic complexity. As a consequence, for every time-bound T(n), there are distributional problems $(L,\mu)$ that can be solved using only a slight increase in time but that cannot be solved on the $\mu$-average in time T(n).

The class NP k V consists of those partial, multivalued functions that can be computed by a nondeterministic, polynomial time-bounded transducer that has at most k distinct values on any input. We define the output-multiplicity hierarchy to consist of the collection of classes NP k V for all positive integers k ≥ 1. In this paper we investigate the strictness of the output-multiplicity hierarchy and establish three main results pertaining to this: 1. 1. If for any k > 1, the class NP k V collapses into the class NP( k − 1)V, then the polynomial hierarchy collapses to Σ 2 P . 2. 2. If the converse of the above result is true, then any proof of this converse cannot relativize. We exhibit an oracle relative to which the polynomial hierarchy collapses to P NP , but the output-multiplicity hierarchy is strict. 3. 3. Relative to a random oracle, the output-multiplicity hierarchy is strict. This result is in contrast to the still open problem of the strictness of the polynomial hierarchy relative to a random oracle. In introducing the technique for the third result we prove a related result of interest: relative to a random oracle UP ≠ NP.

This paper focuses on complexity classes of partial functions that are computed in polynomial time with oracles in NPMV, the class of all multivalued partial functions that are computable nondeterministically in polynomial time. Concerning deterministic polynomial-time reducibilities, it is shown that a multivalued partial function is polynomial-time computable with k adaptive queries to NPMV if and only if it is polynomial-time computable via 2 k-1 nonadaptive queries to NPMV; a characteristic function is polynomial-time computable with k adaptive queries to NPMV if and only if it is polynomial-time computable with k adaptive queries to NP; unless the Boolean hierarchy collapses, for every k, k adaptive (nonadaptive) queries to NPMV are different than k+1 adaptive (nonadaptive) queries to NPMV. Nondeterministic reducibilities, lowness, and the difference hierarchy over NPMV are also studied. The difference hierarchy for partial functions does not collapse unless the Boolean hierarchy collapses, but, surprisingly, the levels of the difference and bounded query hierarchies do not interleave (as is the case for sets) unless the polynomial hierarchy collapses.

We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of coNPMV by showing that it is essentially the same as that of NPMV/sup NP/ complete functions for coNPMV are exhibited and central complexity-theoretic properties of this class are studied. We show that computing maximum satisfying assignments can be done in coNPMV, which leads us to a comparison of NPMV and coNPMV with Krentel's classes Max P and Min P. The difference hierarchy for NPMV is related to the query hierarchy for coNPMV. Finally, we examine a functional analogue of Chang and Kadin's relationship between a collapse of the Boolean hierarchy over NP and a collapse of the polynomial time hierarchy.

We study two properties of a complexity class C-whether there exists a truth-table hard p-selective language for C, and whether polynomially-many nonadaptive queries to C can be answered by making O(log n)-many adaptive queries to C (in symbols, is PF/sub tt//sup C//spl sube/PF/sup C/[O(log n)]). We show that if there exists an NP-hard p-selective set under truth-table reductions, then PF/sub tt//sup NP//spl sube/PF/sup NP/[O(log n)]. We observe that if C/spl supe/P/sup NP/, then these two properties are equivalent. Also, we show that if there exists a truth-table complete standard-left cut in NP, then the polynomial hierarchy collapses to P/sup NP/. We prove that P=NP follows if for some k>0, the class PF/sub tt//sup NP/ is "effectively included" in PF/sup NP/[k[log n]-1].

This paper surveys basic results on complexity classes of partial multivalued functions. We stress basic inclusion relations, interesting hierarchies, and results that demonstrate that hierarchies are extant.

We distinguish self-reducibility of a languageLwith the question of whether search reduces to decision forL. Results include: (i) If NE≠E, then there exists a setLin NP−P such that search reduces to decision forL, search doesnotnonadaptively reduce to decision forLandLis not self-reducible. (ii) If UE≠E, then there exists a languageL∈UP−P such that search nonadaptively reduces to decision for L, but L is not self-reducible. (iii) If UE∩co-UE≠E, then there is a disjunctive self-reducible languageL∈UP−P for which search doesnotnonadaptively reduce to decision. We prove that if NE⊈BPE, then there is a languageL∈NP−BPP such thatLis randomly self-reducible,notnonadaptively randomly self-reducible, andnotself-reducible. We obtain results concerning trade-offs in multiprover interactive proof systems and results that distinguish checkable languages from those that are nonadaptively checkable. Many of our results are proven by constructing p-selective sets. We obtain a p-selective set that isnot⩽Ptt-equivalent to any tally language, and we show that if P=PP, then every p-selective set is ⩽PT-equivalent to a tally language. Similarly, if P=NP, then every cheatable set is ⩽Pm-equivalent to a tally language. We construct a recursive p-selective tally set that isnotcheatable.

Is there an NP function that, when given a satisfiable formula as input, outputs one satisfying assignment uniquely? That is, can a nondeterministic function cull just one satisfying assignment from a possibly exponentially large collection of assignments? We show that if there is such a nondeterministic function, then the polynomial hierarchy collapses to ${\text{ZPP}}^{{\text{NP}}} $ (and thus, in particular, to ${\text{NP}}^{{\text{NP}}} $). Because the existence of such a function is known to be equivalent to the statement “every NP function has an NP refinement with unique outputs,” our result provides the strongest evidence yet that NP functions cannot be refined. We prove our result via a result of independent interest. We say that a set A is NPSV-selective (NPMV-selective) if there is a 2-ary partial NP function with unique values (a 2-ary partial NP function) that decides which of its inputs (if any) is “more likely” to belong to A; this is a nondeterministic analog of the recursion-theoretic notion of the semirecursive sets and the extant complexity-theoretic notion of P-selectivity. Our hierarchy-collapse result follows by combining the easy observation that every set in NP is NPMV-selective with the following result: If $A \in {\text{NP}}$ is NPSV-selective, then $A \in {{({\text{NP}} \cap {\text{coNP}})} / {{\text{poly}}}}$. Relatedly, we prove that if $A \in {\text{NP}}$ is NPSV-selective, then A is ${\text{Low}}_2 $. We prove that the polynomial hierarchy collapses even further, namely to NP, if all coNP sets are NPMV-selective. This follows from a more general result we prove: Every self-reducible NPMV-selective set is in NP.

There exists an oracle, relative to which, P ≠ NP, and each of the following properties hold: (i)All Σ2P-complete sets are p-isomorphic; (ii)P-inseparable pairs of sets in NP do not exist; (iii)Intractable public-key cryptosystems do not exist; (iv)NP-complete sets are closed under union of disjoint sets. Remarkably, these properties all follow from one oracle construction. Namely, we prove that there is an oracle A such that every two disjoint sets in NPA are P-separable, and Σ2P = U DTIME(2P)| p is a polynomial. Additional related relativization results are presented also.

A general theory of public-key cryptography is developed that is based on the mathematical framework of complexity theory. Two related approaches are taken to the development of this theory, and these approaches correspond to different but equivalent formulations of the problem of cracking a public-key cryptosystem (PKCS). The first approach is to model the cracking problem as a partial decision problem called a “promise problem.” Every NP-hard promise problem is shown to be uniformly NP-hard, and a number of results and a conjecture about promise problems are shown to be equivalent to separability assertions for sets in NP that are the natural analogues of well-known results in classical recursion theory. The conjecture, if it is true, implies nonexistence of PKCS having NP-hard cracking problems. The second approach represents the cracking problem of a PKCS as a partial computational problem directly. Using this approach, it is shown that one-way functions exist if and only if ${\text{P}} \ne {\text{UP}}$ and that one-way functions with greater cryptographic significance exist if and only if NP contains disjoint P-inseparable sets. The paper concludes with a discussion of almost-everywhere security measures for PKCS.

To every set A in NP we associate a (collection of) natural self-reducible set${\operatorname{set}}(s)$. We prove that every disjunctive-self-reducible set in NP is $ \leqq _d^P $-equivalent to one of these natural self-reducible sets and we show that if certain questions about these sets could be answered, then several significant open questions about the fine structure of NP would be solved.

Baker, Gill, and Solovay constructed sparse sets A and B such that P( A ) ≠ NP( A ) and NP( B ) ≠ co-NP( B ). In contrast to their results, we prove that P = NP if and only if for every tally language T , P( T ) = NP( T ), and that NP = co-NP if and only if for every tally language T , NP( T ) = co-NP( T ). We show that the polynomial hierarchy collapses if and only if there is a sparse set S such that the polynomial hierarchy relative to S collapses. Similar results are obtained for several other complexity classes.

Nancy Lynch proved that if a decision problem A is not solvable in polynomial time, then there exists an infinite recursive subset X of its domain on which the decision is almost everywhere complex. In this paper, general theorems of this kind that can be applied to several well-known automata-based complexity classes, including a common class of randomized algorithms, are proved.

We show that several questions about the polynomial-time hierarchy can be answered by answering their counterparts for the polynomial-time hierarchy relativized to an arbitrary sparse oracle set. For each of these questions, the answer will be the same for the hierarchy relativized to S/sub 1/ as it will be for the hierarchy relativized to S/sub 2/ for any choice of S/sub 1/ and S/sub 2/ that are sparse sets, including the choice of S/sub 1/ being empty and S/sub 2/ being nonempty but sparse.

The first part of this paper gives results about promise problems. A "promise problem" is a formulation of a partial decision problem that is useful for describing cracking problems for public-key cryptosystems (PKCS). We prove that every NP-hard promise problem is uniformly NP-hard, and we show that a number of results and a conjecture about promise problems are equivalent to separability assertions that are the natural analogues of well-known results in classical recursion theory. The conjecture, if it is true, implies nonexistence of PKCS having NP-hard cracking problems. The second part of the paper studies more appropriate measures for PKCS. Among the results obtained are the following: One-way functions exist if an only if P /spl ne/ U and one-way functions f such that range f /spl epsiv/ P exist if and only if U /spl cap/ co-U /spl ne/ P. It will allow that there exist PKCS that cannot be cracked in polynomial time (and that satisfy other reasonable assumptions) only if P /spl ne/ U.

Consider the following open problems: (i) ${\text{P}} = ? {\text{ NP}}$ (ii) ${\text{NP}} = ? {\text{ co-NP}}$; (iii) ${\text{P}} = ? {\text{ PSPACE}}$; (iv) ${\text{NP}} = ? {\text{ PSPACE}}$. In this paper we study these four problems from a particular point of view. To illustrate our approach, consider the first problem. It is known that there exist recursive sets A and B such that ${\text{P}}(A) = {\text{NP}}(A)$ and ${\text{P}}(B) \ne {\text{NP}}(B)$. We study restrictions R on both the deterministic and also the nondeterministic polynomial time-bounded oracle machines such that the following holds: ${\text{P}} = {\text{NP}}$ if and only if for every set A, ${\text{P}}_R (A) = {\text{NP}}_R (A)$. The restrictions are “quantitative” in the sense that the size of the set of strings queried by the oracle in computations of a machine on an input is bounded by a polynomial in the length of the input. We study several different ways of specifying such quantitative restrictions, each of which has the desired property.

Due to the work of Baker, Gill and Solovay [SIAM J. Comput., 4 (1975), pp. 431–442] and others, it has become a paradigm that important open questions about complexity classes do not relativize. This paper develops restrictions of the standard oracle machine model for which, in contrast, positive inclusion relationships do relativize. Our results are obtained by uniform simulation techniques. As a consequence, the new oracle machine models exhibit the same computational power as do the corresponding nonrelativized devices.

A viable polynomial time enumeration reducibility is defined and studied. Let $ \leqq _{{\text{pe}}} $ denote this reducibility. $ \leqq _{{\text{pe}}} $ is intrinsic to certain tradeoffs between nondeterministic oracle recognition of sets and deterministic oracle computations between functions. A set belongs to $\mathcal{NP}$ if and only if the set is, in some natural sense, polynomial enumerable. $ \leqq _{{\text{pe}}} $ is defined so that $A \leqq _{{\text{pe}}} B$ just in case for every set C, every polynomial enumeration of B relative to C yields some polynomial enumeration of A relative to C. Various properties of $ \leqq _{{\text{pe}}} $ are shown. In particular, $ \leqq _{{\text{pe}}} $ is a maximal transitive subrelation of $ \leqq _{\text{T}}^{\mathcal{NP}} $. Also, $ \leqq _{{\text{pe}}} $ is equal to $ \leqq _{\text{c}}^{\mathcal{NP}} $ on low level complexity classes, but the equality does not hold over all recursive sets.

Some of the questions posed by Baker, Gill, and Solovay [1] are here answered. The principal result is that there exists a recursive oracle for which the relativized polynomial hierarchy exists through the second level; that is, there is a recursive set B such that Σ2P,B ≠ π2P,B. It follows that Σ2P,B ⊂≠ Σ3P,B.

Comparison of the polynomial-time-bounded reducibilities introduced by Cook [1] and Karp [4] leads naturally to the definition of several intermediate truth-table reducibilities. We give definitions and comparisons for these reducibilities; we note, in particular, that all reducibilities of this type which do not have obvious implication relationships are in fact distinct in a strong sense. Proofs are by simultaneous diagonalization and encoding constructions.Work of Meyer and Stockmeyer [7] and Gill [2] then leads us to define nondeterministic versions of all of our reducibilities. Although many of the definitions degenerate, comparison of the remaining nondeterministic reducibilities among themselves and with the corresponding deterministic reducibilities yields some interesting relationships.

H. Scholz [11] defined the spectrum of a formula φ of first-order logic with equality to be the set of all natural numbers n for which φ has a model of cardinality n. He then asked for a characterization of spectra. Only partial progress has been made. Computational aspects of this problem have been worked on by Gunter Asser [1], A. Mostowski [9], and J. H. Bennett [2]. It is known that spectra include the Grzegorczyk class and are properly included in . However, no progress has been made toward establishing whether spectra properly include , or whether spectra are closed under complementation. A possible connection with automata theory arises from the fact that contains just those sets which are accepted by deterministic linear-bounded Turing machines (Ritchie [10]). Another resemblance lies in the fact that the same two problems (closure under complement, and proper inclusion of ) have remained open for the class of context sensitive languages for several years. In this paper we show that these similarities are not accidental—that spectra and context sensitive languages are closely related, and that their open questions are merely special cases of a family of open questions which relate to the difference (if any) between deterministic and nondeterministic time or space bounded Turing machines. In particular we show that spectra are just those sets which are acceptable by nondeterministic Turing machines in time 2cx, where c is constant and x is the length of the input. Combining this result with results of Bennett [2], Ritchie [10], Kuroda [7], and Cook [3], we obtain the “hierarchy” of classes of sets shown in Figure 1. It is of interest to note that in all of these cases the amount of unrestricted read/write memory appears to be too small to allow diagonalization within the larger classes.

In this paper we show that these similarities are not accidental - that spectra and context sensitive languages are closely related, and that their open questions are merely special cases of a family of open questions which relate to the difference (if any) between deterministic and non-deterministic time-or space-bounded Turing machines.