Studies in Bounded Query Hierarchies
This item is restricted to only allow viewing of the metadata.

Title
Studies in Bounded Query Hierarchies
Author
Purini , Venkata Suresh Reddy
Advisors
Chang , Richard
Program
Computer Science
UMBC Department
Computer Science and Electrical Engineering
Document Type
dissertation
Sponsors
University of Maryland , Baltimore County (UMBC)
Keywords
Computer Science (0984) ; Mathematics (0405)
Date Issued
2008-10-14 ;
Abstract
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 .
Identifier
1252
Format
application:pdf
Language
en
Collection
UMBC Theses and Dissertations
Rights Statement
This item may be protected under Title 17 of the U.S. Copyright Law. It is made available by UMBC for non-commercial research and education. For permission to publish or reproduce, please see http://library.umbc.edu/speccoll/rightsreproductions.php or contact Special Collections at speccoll(at)umbc.edu.
Source
umi-umbc-1252.pdf
Access Rights
Access limited to the UMBC community. Item may possibly be obtained via Interlibrary Loan through a local library, pending author/copyright holder's permission.

Add tags for Studies in Bounded Query Hierarchies

you wish to report:

Your comment:

Your Name:

...