This paper shows a complete upward collapse in the Polynomial Hierarchy (PH) if for ZPP, two queries to a SAT oracle is equivalent to one query. That is, ZPPSAT[1]= ZPPSAT||[2]rArr ZPPSAT[1]= PH. These ZPP machines are required to succeed with probability at least 1/2 + 1/p(n) on inputs of length n for some polynomial p(n). This result builds upon recent work by Tripathi who showed a collapse of PH to S2P. The use of the probability bound of 1/2 + 1/p(n) is justified in part by showing that this bound can be amplified to 1 - 2-nkfor ZPPSAT[1]computations. This paper also shows that in the deterministic case, PSAT[1]= PSAT||[2]rArr PH sube ZPPSAT[1]where the ZPPSAT[1]machine achieves a probability of success of 1/2 - 2-nk.

The NP machine hypothesis posits the existence of an \in \ge 0 and a nondeterministic polynomial-time Turing machine M which accepts the language 0 but for which no deterministic Turing machine running in 2^n time can output an accepting path infinitely often. This paper shows two applications of the NP machine hypothesis in bounded query complexity. First, if the NP machine hypothesis holds, then P^SAT[1] = P^SAT[2] \Rightarrow PH \subseteq NP. Without assuming the NP machine hypothesis, the best known collapse of the Polynomial Hierarchy (PH) is to the class S_2^P due to a result of Fortnow, Pavan and Sengupta [9]. The second application is to bounded query function classes. If the NP machine hypothesis holds then for all constants d \ge 0, there exists a constant k \ge d such that for all oracles X, PF^SAT[n^k] \not\subset PF^X[n^d]. In particular, PF^SAT[n^d] \varsubsetneq PF^SAT[n^k]. Without the NP machine hypothesis, there are currently no known consequences even if for all k \ge 1, PF^SAT[n^k] \subseteq PF^SAT[n].

The paper explores the difference between parallel and serial queries to an NP-complete oracle, SAT, from the perspective of functions with a limited number of output bits. For polynomial-time bounded query language classes, which can be considered as functions with 1 bit output, previous work has shown that 2 serial queries to SAT is equivalent to 3 parallel queries to SAT. In contrast, for function classes with no limit on the number of output bits, previous work has shown that there exists a function that can be computed in polynomial time using 3 parallel queries to SAT, but cannot be computed using 2 serial queries to SAT, unless P=NP. The results show that there exists a function with 2 bit output that can be computed using 3 parallel queries to SAT, but cannot be computed using 2 serial queries to SAT, unless the polynomial hierarchy collapses.

This paper investigates the computational complexity of approximating several \NP-optimization problems using the number of queries to an \NP\ oracle as a complexity measure. The results show a tradeoff between the closeness of the approximation and the number of queries required. For an approximation factor $k(n)$, $\log \log_{k(n)} n$ queries to an \NP\ oracle can be used to approximate the maximum clique size of a graph within a factor of $k(n)$. However, this approximation cannot be achieved using fewer than $\log \log_{k(n)} n - c$ queries to any oracle unless $\Pe = \NP$, where c is a constant that does not depend on k. These results hold for approximation factors $k(n) \geq 2$ that belong to a class of functions which includes any integer constant function, $\log n$, $\log^{a} n$, and $n^{1/a}$. Similar results are obtained for Graph Coloring, Set Cover, and other \NP-optimization problems.

We show that if the Boolean hierarchy collapses to level k, then the polynomial hierarchy collapses to ${\text{BH}}_3 (k)$, where ${\text{BH}}_3 (k)$ is the kth level of the Boolean hierarchy over $\Sigma _2^{\text{P}} $. This is an improvement over the known results, which show that the polynomial hierarchy would collapse to ${\text{P}}^{{\text{NP}}^{{\text{NP}}} } [O(\log n)]$. This result is significant in two ways. First, the theorem says that a deeper collapse of the Boolean hierarchy implies a deeper collapse of the polynomial hierarchy. Also, this result points to some previously unexplored connections between the Boolean and query hierarchies of $\Delta _2^{\text{P}} $ and $\Delta _3^{\text{P}} $. Namely,\[ \begin{gathered} {\text{BH}}(k) = {\text{co - BH}}(k) \Rightarrow {\text{BH}}_3 (k) = {\text{co - BH}}_3 (k), \\ {\text{P}}^{{\text{NP}}} \|[k] = {\text{P}}^{{\text{NP}}} \|[k + 1] \Rightarrow {\text{P}}^{{\text{NP}}^{{\text{NP}}} } \|[k + 1] = {\text{P}}^{{\text{NP}}^{{\text{NP}}} } \|[k + 2]. \\ \end{gathered} \]

The research presented in this paper is motivated by the some new results on the complexity of the unique satisfiability problem, USAT. These results, which are shown for the first time in the paper, are: if USAT ≡ , then D = co-D and PH collapses. if USAT ∈ co-D, then PH collapses. if USAT has OR, then PH collapses.

The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the unrelativized case. Although this paper is not the first to provide a counterexample to the Random Oracle Hypothesis, it does provide a most compelling counterexample by showing that for almost all oracles A, IPA ≠ PSPACEA. If the Random Oracle Hypothesis were true, it would contradict Shamir's result that IP = PSPACE. In fact, it is shown that for almost all oracles A, co-NPA ⫋ IPA. These results extend to the multiprover proof systems of Ben-Or, Goldwasser, Killian, and Wigderson. In addition, this paper shows that the Random Oracle Hypothesis is sensitive to small changes in the definition. A class IPP, similar to IP, is defined. Surprisingly, the IPP = PSPACE result holds for all oracle worlds.

This paper investigates the computational complexity of approximating NP-optimization problems using the number of queries to an NP oracle as a complexity measure. The results show a trade-off between the closeness of the approximation and the number of queries required. For an approximation factor k(n), loglog/sub k(n/) n queries to an NP oracle can be used to approximate the maximum clique size of a graph within a factor of k(n). However, this approximation cannot be achieved using fewer than loglog/sub k(n/) n-c queries to any oracle unless P=NP, where c is a constant that does not depend on k. These results hold when k(n) belongs to a class of functions which include any integer constant function, log n, log/sup a/ n and n/sup 1/a/. Similar results are obtained for graph coloring, set cover and other NP-optimization problems.>

Kadin [SIAM J. Comput., 17 (1988), pp. 1263–1282] showed that if the polynomial hierarchy (PH) has infinitely many levels, then for all k, ${\text{P}}^{{\operatorname{SAT}}[k]} \subset {\text{P}}^{{\operatorname{SAT}}[K + 1]} $. This paper extends Kadin’s technique and shows that a proper query hierarchy is not an exclusive property of NP complete sets. In fact, for any $A \in {\text{NP}} - \widehat{{\text{low}}}_{3} $, if PH has infinitely many levels, then ${\text{P}}^{A[k]} \subset {\text{P}}^{A[K + 1]} $. Moreover, for the case of parallel queries, ${\text{P}}^{A||[k + 1]} $ is not even contained in ${\text{P}}^{{\operatorname{SAT}}||[K]} $ , These same techniques can be used to explore some other questions about query hierarchies. For example, if there exists any A such that ${\text{P}}^{A[2]} = {\text{P}}^{{\operatorname{SAT}}[1]} $, then PH collapses to $\Delta _3^P $.

In this paper we review the key results about space bounded complexity classes, discuss the central open problems and outline the prominent proof techniques. We show that, for a slightly modified Turing machine model, low level deterministic and nondeterministic space bounded complexity classes are different. Furthermore, for this computation model, we show that Savitch's theorem and the Immerman-Szelepcsényi theorem do not hold in the range lg lg n to lg n. We also present other changes in the computation model which bring out and clarify the importance of space constructibility. We conclude by enumerating open problems which arise out of the discussion.