Adaptive versus nonadaptive queries to NP and P-selective sets

AV Naik, AL Selman - computational complexity, 1999 - Springer
AV Naik, AL Selman
computational complexity, 1999Springer
We prove that P= NP follows if for some k>0, the class \rmPF^\rmNP_tt of functions that are
computable in polynomial time by nonadaptively accessing an oracle in NP is effectively
included in PF NP k⌈ log n⌉—1, the class of functions that are computable in polynomial k⌈
log n⌉—1 queries to an oracle in NP.¶ We draw several observations and relationships
between the following two properties of a complexity class \calC: whether there exists a
truthtable hard p-selective language for \calC, and whether polynomially-many nonadaptive …
Abstract
We prove that P = NP follows if for some , the class of functions that are computable in polynomial time by nonadaptively accessing an oracle in NP is effectively included in PFNP[k⌈log n⌉— 1], the class of functions that are computable in polynomial k⌈log n⌉— 1 queries to an oracle in NP.¶We draw several observations and relationships between the following two properties of a complexity class : whether there exists a truthtable hard p-selective language for , and whether polynomially-many nonadaptive queries to can be answered by making O(log n)-many adaptive queries to (in symbols, whether ). Among these, we show that if there exists an NP-hard p-selective set under truth-table reductions, then . However, if , then these two properties are equivalent.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果