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
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.7
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb