Do more queries to SAT allow us to compute more functions? It is known that when f(n) = O(log n), where n is the input length, the set of functions computable by polynomial-time Turing machines (PTMs) asking f( n)+1 SAT oracle queries is strictly larger than that computable using just f(n) SAT queries, unless the Polynomial Hierarchy (PH) collapses. However, when f(n) grows super-logarithmically, we do not know whether f( n) + 1 SAT queries are more powerful than f( n) SAT queries. Under the NP-machine hypothesis, we show that when f(n) = ω(log n), there exists a function g(n) > f( n) such that PF^{SAT[f (n)]} [special characters omitted] PF^{SAT[g( n)]}.

Informally, the NP-machine hypothesis is a uniform hardness assumption on NP search problems. The NP-machine hypothesis posits the existence of an ε > 0 and a nondeterministic PTM which accepts the language 0* but for which no deterministic Turing machine running in [special characters omitted] time can output an accepting path infinitely often. We make use of the NP-machine hypothesis to answer another interesting question in the area of bounded query hierarchies, "What is the best PH collapse we can achieve if PTMs with access to only one SAT query can recognize the same set of languages as those with access to two SAT queries?" We show that under the NP-machine hypothesis if P^SAT[1] = ^{PSAT∣∣[2]}, then PH collapses down to NP. Without the NP-machine hypothesis the best previously known collapse is down to [special characters omitted] a complexity class which lies in [special characters omitted]

Are two SAT queries more powerful than a single SAT query when the base machine is a ZPP computation? It is known that even if P^SAT∣∣[2] ⊆ [special characters omitted] where 1/poly is the success probability of the ZPP computation, then PH collapses to its third level. In this thesis we show that if [special characters omitted] then PH collapses to [special characters omitted] We also prove that the success probability of a ZPP^SAT[1] computation can be amplified by showing that [special characters omitted] and [special characters omitted] Further, we show certain limitations on the amplifiability of the success probability for ZPP^{SAT∣∣[k ]} computations, for constant k > 1.

We also study the difference between serial and parallel SAT oracle access mechanisms with respect to functions having limited output bits. We know that for languages P^{SAT[k ]} = P^{SAT∣∣[2k -1]} whereas for functions PF^{SAT[k ]} = PF^{SAT∣∣[2k -1]} implies P = NP. What about the functions which are limited to j bits of output? Do they behave similar to languages or similar to functions with unlimited output bits? In this thesis we show that PH collapses to its third level if [special characters omitted] for any k, j > 0 and l 2 ^k-j+1 + j - 1. Using a census argument, we can show that [special characters omitted] However, when l ∈ [2^k-j, 2^k-j+1 - j + 1], the status of the problem remains open.