×

On the structure of bounded queries to arbitrary NP sets. (English) Zbl 0749.68034

Summary: J. Kadin[SIAM J. Comp., 17, 1263-1282 (1988; Zbl 0664.03031)] showed that if the polynomial hierarchy (PH) has infinitely many levels, then for all \(k\) \(\text{P}^{\text{SAT}[k]}\subset\text{P}^{\text{SAT}[k+1]}\). This paper extends Kadin’s technique and shows that a proper query hierarchy is not an exclusive property of NP complete sets. In fact, for any \(A \in\text{NP}-\widetilde{\text{low}}_ 3\), if PH has infinitely many levels, then P\(^{A[k]}\subset\text{P}^{A[k+1]}\). Moreover, for the case of parallel queries, P\(^{A\| [k+1]}\) is not even contained in P\(^{\text{SAT}\| [k]}\). These same techniques can be used to explore some other questions about query hierarchies. For example, if there exists any \(A\) such that \(\text{P}^{A[2]} =\text{P}^{\text{SAT}[1]}\), then PH collapses to \(\Delta_ 3^{\text{P}}\).

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
03D20 Recursive functions and relations, subrecursive hierarchies

Citations:

Zbl 0664.03031
PDFBibTeX XMLCite
Full Text: DOI Link