Studies in Bounded Query Hierarchies

The area of bounded query hierarchies studies the question ``Does more queries to an oracle X help?"" This question helps us understand the structural complexity of the language X. In this thesis, we specifically study bounded query hierarchies with respect to the SAT oracle. We show that under the NP-machine hypothesis, for every function f(n) exists a function g(n) such that g(n)>f(n) and the set of functions computable by polynomial time Turing machines (PTMs) with access to g(n) SAT oracle queries strictly contains the set of functions computable by PTMs with access to f(n) SAT queries. Previously, we know that if f(n)=O(log n),then f(n)+1 SAT queries are strictly more powerful than f(n) SAT queries unless Polynomial Hierarchy (PH) collapses. Our result supports this claim even if f(n) grows super-logarithmically using the NP-machine hypothesis. Informally, NP-machine hypothesis is a uniform hardness assumption on the NP-search problems. 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 if the NP-machine hypothesis is true and if two SAT queries are no more powerful than a single SAT query, then PH collapses down to NP. Without the NP-machine hypothesis, the best known PH collapse under the two queries assumption is up to its second level. Are two SAT queries more powerful than a single SAT query when the base machines are ZPP computations? The answer to this question is negative unless the PH collapses to its second level. In this thesis we improve the collapse of PH by showing that ZPP machines can decide all the languages in PH using just one SAT query and with a success probability of 1/2+1/poly. We assume that the success probability of the ZPP computations is 1/2+1/poly. We also prove that the success probability of ZPP computations which ask at most one SAT query can be amplified from 1/poly to 1/4 and from 1/2+1/poly to 1-1/exp. Based on previous results, we also show certain limitations on success probability amplification for ZPP computations asking more than one SAT query. 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 k serial SAT queries have the same power as 2^k-1 parallel SAT queries, whereas for functions this would imply that P=NP. What about the functions which are limited to j bits? Do they behave similar to languages or similar to functions with unlimited output bits? In this thesis we show that with respect to j-bit functions, l parallel SAT queries are strictly more powerful than k serial SAT queries unless PH collapses to its third level for l>2^{k-j+1}+j. Using a census argument, it can be shown that any j-bit function computable by a PTM asking 2^{k-j}-1 parallel SAT queries is also computable using k-serial SAT queries