Studies in bounded query hierarchies
Richard Chang, Venkata Suresh Reddy Purini · 2008
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 PFSAT[f (n)] s PFSAT[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 e > 0 and a nondeterministic PTM which accepts the language 0* but for which no deterministic Turing machine running in 2ne 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, 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 PSAT[1] = PSATmm[2], then PH collapses down to NP. Without the NP-machine hypothesis the best previously known collapse is down to SP2, a complexity class which lies in 2 P b 2 P . 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 PSATmm[2] ⊆ ZPPSAT1 1/poly, 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 ZPPSATd2 1-1/exp⊆ZPPSAT1 1/2+1/poly, then PH collapses to ZPPSAT1 1/2+1/poly. We also prove that the success probability of a ZPPSAT[1] computation can be amplified by showing that ZPPSAT1 1/poly⊆ZPPSAT1 1/4 and ZPPSAT1 1/2+1/poly⊆ZPPSAT1 1-1/exp. Further, we show certain limitations on the amplifiability of the success probability for ZPPSATmm[k ] computations, for constant k > 1. We also study the difference between serial and parallel SAToracle access mechanisms with respect to functions having limited output bits. We know that for languages PSAT[k ] = PSATmm[2k -1] whereas for functions PFSAT[k ] = PFSATmm[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 PFSATdl j⊆PFSAT kj, for any k, j > 0 and l 2 k-j+1 + j - 1. Using a census argument, we can show that PFSATd2k-j-1 j ⊆PFSATk j. However, when l ∈ [2k-j, 2k-j+1 - j + 1], the status of the problem remains open.