\(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP (Q908700): Difference between revisions

It has been known (\textit{S. Mahaney} [J. Comput. Syst. Sci. 25, 130-143 (1987; Zbl 0493.68043)] that the polynomial hierarchy collapses to \(P^{NP}\) if NP has a \(\leq^ P_ T\)-complete sparse set. The author improves this result by replacing \(N^{NP}\) with \(P^{NP[O(\log n)]}\), where this latter class is the class of all languages acceptable by deterministic polynomial time machines making only O(log n) queries to an NP-oracle. This result is a consequence of the following one: If for a sparse S in NP it holds that \(coNP\subseteq NP^ S\), then \(PH\subseteq P^{NP[O(\log n)]}\). This collapse result is optimal in the following sense: For any function \(f(n)=o(\log n)\) there exists a set B for which \(NP^ B\) has a sparse \(\leq^ P_ T\)-complete set and \((P^ B)^{NP^ B[O(\log n)]}\subseteq (P^ B)^{NP^ B[f(n)]}.\) Furthermore, the paper exhibits \(\leq^ P_ m\)-complete problems for \(P^{NP[O(\log n)]}\) and discusses conditions fo the class of languages \(\leq^ P_ m\)-reducible to a set C to be equal to \(P^{C[O(\log n)]}\). For \(D^ P=\{X\cap Y :\) \(X\in NP\wedge Y\in coNP\}\) it is shown: If \(D^ P=coD^ P\), then \(P^{NP[O(\log n)]}\subseteq D^ P\).