loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07)
Bounded Queries and the NP Machine Hypothesis
San Diego, California
June 13-March 16
ISBN: 0-7695-2780-9
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.