loading...
Bounded Queries and the NP Machine Hypothesis
San Diego, California June 13-March 16
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.7Twenty-Second Annual IEEE Conference ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Richard Chang, University of Maryland Baltimore County, USA
Suresh Purini, University of Maryland Baltimore County, USA
The NP machine hypothesis posits the existence of an \in \ge 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 time can output an accepting path infinitely often. This paper shows two applications of the NP machine hypothesis in bounded query complexity. First, if the NP machine hypothesis holds, then

P^SAT[1] = P^SAT[2] \Rightarrow PH \subseteq NP.

Without assuming the NP machine hypothesis, the best known collapse of the Polynomial Hierarchy (PH) is to the class S_2^P due to a result of Fortnow, Pavan and Sengupta [9].

The second application is to bounded query function classes. If the NP machine hypothesis holds then for all constants d \ge 0, there exists a constant k \ge d such that for all oracles X,

PF^SAT[n^k] \not\subset PF^X[n^d].

In particular, PF^SAT[n^d] \varsubsetneq PF^SAT[n^k]. Without the NP machine hypothesis, there are currently no known consequences even if for all k \ge 1, PF^SAT[n^k] \subseteq PF^SAT[n].

Citation:
Richard Chang, Suresh Purini, "Bounded Queries and the NP Machine Hypothesis," ccc, pp.52-59, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.