# zbMATH — the first resource for mathematics

$$P^{NP[O(\log n)]}$$ and sparse turing-complete sets for NP. (English) Zbl 0693.68027
It has been known (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$$.
Reviewer: G.Wechsung

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 03D15 Complexity of computation (including implicit computational complexity) 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 03D10 Turing machines and related notions 68Q45 Formal languages and automata
Full Text: