A note on p-selective sets and on adaptive versus nonadaptive queries to NP
Ashish V. Naik, Alan L. Selman · 2002
We study two properties of a complexity class C-whether there exists a truth-table hard p-selective language for C, and whether polynomially-many nonadaptive queries to C can be answered by making O(log n)-many adaptive queries to C (in symbols, is PF/sub tt//sup C//spl sube/PF/sup C/[O(log n)]). We show that if there exists an NP-hard p-selective set under truth-table reductions, then PF/sub tt//sup NP//spl sube/PF/sup NP/[O(log n)]. We observe that if C/spl supe/P/sup NP/, then these two properties are equivalent. Also, we show that if there exists a truth-table complete standard-left cut in NP, then the polynomial hierarchy collapses to P/sup NP/. We prove that P=NP follows if for some k>0, the class PF/sub tt//sup NP/ is "effectively included" in PF/sup NP/[k[log n]-1].