Chang, Richard On the structure of bounded queries to arbitrary NP sets. (English) Zbl 0749.68034 SIAM J. Comput. 21, No. 4, 743-754 (1992). 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}}\). Cited in 3 Documents 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 Keywords:polynomial-time hierarchy; Boolean hierarchy; bounded queries; sparse sets; nonuniform computation Citations:Zbl 0664.03031 × Cite Format Result Cite Review PDF Full Text: DOI Link