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:
  • Article in IEEE Xplore: DOI 10.1109/CCC.2007.7
  • Conference submission: QQNPMH.pdf (PDF 152kbytes).

Abstract:

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.