Bounded Queries and the NP Machine Hypothesis


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