####
Bounded Queries and the NP Machine Hypothesis

- Authors: R. Chang and S. Purini
- Cite as:
In
*Proceedings of the 22nd IEEE Conference on Computational Complexity*, 52–59, June 2007.
- Previous incarnations: none.
- Most readable version:
conference version.
- Status: journal version under preparation.
- On-line:

#### Abstract:

The NP machine hypothesis posits the existence of an epsilon > 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^epsilon) time can output an accepting path infinitely often. This
paper shows two applications of the NP machine hypothesis in bounded query
complexity.
First, assuming the NP machine hypothesis holds, if polynomial-time oracle
Turing machines with only one query to the SAT oracle can recognize all the
languages recognized by such machines with two oracle queries to SAT, then
the Polynomial Hierarchy (PH) collapses to NP. Without assuming the NP
machine hypothesis, the best known collapse of PH is to the class S_2^P due
to a result of Fortnow, Pavan and Sengupta.

The second application is to bounded query function classes. If the NP
machine hypothesis holds then for all constants d > 0, there exists a
constant k > d such that for all oracles X, there exists a function
computable by polynomial-time Turing machines using n^k oracle queries to
SAT, that cannot be computed by such machines with n^d oracle queries to X.
In particular, n^d oracle queries
to SAT is strictly less powerful than n^k queries to SAT. Without the NP
machine hypothesis, there are currently no known
consequences even if for all k > 1, every function computable using n^k
queries to SAT can be computed by some machine using only
n queries to SAT.

Last Modified:
29 Aug 2008 13:45:40 EDT
by
Richard Chang