Lozano, A. Bounded queries to arbitrary sets. (English) Zbl 0860.68047 RAIRO, Inform. Théor. Appl. 30, No. 2, 91-100 (1996). Summary: We prove that if \(\text{P}^A_{k\text{-}T}=\text{P}^A_{(k+1)\text{-}T}\) for some \(k\) and an arbitrary set \(A\), then \(A\) is reducible to its complement under a relativized nondeterministic conjunctive reduction. By substituting \(A\) by different sets, we derive some known facts such as Kadin’s theorem and its extension to the class \(\text{C}_=\text{P}\). MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) Keywords:hierarchy of sets PDFBibTeX XMLCite \textit{A. Lozano}, RAIRO, Inform. Théor. Appl. 30, No. 2, 91--100 (1996; Zbl 0860.68047) Full Text: DOI EuDML References: [1] 1. E. ALLENDER, L. A. HEMACHANDRA, M. OGIWARA, and O. WATANABE, Relating equivalence and reducibility to sparse sets, SIAM Journal on Computing, 1992, 2, pp. 521-539. Zbl0761.68039 MR1163344 · Zbl 0761.68039 [2] 2. A. AMIR, R. BEIGEL and W. I. GASARCH, Some connections between bounded query classes and non-uniform complexity, Proceedings of the 5th Structure in Complexity Theory Conference, 1990, pp. 232-243. MR1097673 · Zbl 1058.68056 [3] 3. R. BEIGEL, Query-limited Reducibilities, PhD thesis, Stanford University, 1987. MR2636225 [4] 4. R. BEIGEL, Bounded queries to SAT and the boolean hierarchy, Theoretical Computer Science, 1991, 84 (2), pp. 199-223. Zbl0739.68035 MR1118121 · Zbl 0739.68035 [5] 5. R. BEIGEL, R. CHANG, and M. OGIWARA, A relationship between difference hierarchies and relativized polynomial hierarchies, Mathematical Systems Theory, 1993, 26 (3), pp. 293-310. Zbl0776.68043 MR1209999 · Zbl 0776.68043 [6] 6. R. CHANG, On the structure of bounded queries to arbitrary NP sets, SIAM Journal on Computing, 1992, 21 (4), pp. 743-754. Zbl0749.68034 MR1171859 · Zbl 0749.68034 [7] 7. R. CHANG and J. KADIN, The boolean hierarchy and the polynomial hierarchy: a closer connection, Proceedings of the 5th Structure in Complexity Theory Conference, 1990, pp. 169-178. To appear in SIAM Journal on Computing. Zbl0844.68048 MR1097667 · Zbl 0844.68048 [8] 8. F. GREEN, On the power of deterministic reductions to C = P, Manuscript, April 1991. [9] 9. T. GUNDERMAN, N. NASSER, and G. WECHSUNG, A survey of counting classes, Proceedings of the 5th Structure in Complexity Theory Conference, 1990, pp. 140-153. MR1097665 [10] 10. L. A. HEMACHANDRA, Counting in structural complexity theory, PhD thesis, Cornell University, June 1987. [11] 11. J. KADIN, IS one NP question as powerful as two?, Technical Report TR 87-842, Cornell University, June 1987. [12] 12. J. KADIN, Restricted Turing reducibilities and the structure of the Polynomial Time Hierarchy, PhD thesis, Cornell University, February 1988. · Zbl 0664.03031 [13] 13. J. KADIN, The polynomial time hierarchy collapses if the boolean hierarchy collapses, SIAM Journal on Computing, 1988, 17 (6), pp. 1263-1282. Zbl0664.03031 MR972673 · Zbl 0664.03031 [14] 14. J. KADIN, Erratum to [13], SIAM Journal on Computing, 1991, 20 (2), p. 104. MR1087757 [15] 15. R. E. LADNER, N. A. LYNCH, and A. L. SELMAN, A comparison of polynomial time reducibilities, Theoretical Computer Science, 1975, 1, pp. 103-123. Zbl0321.68039 MR395319 · Zbl 0321.68039 [16] 16. M. OGIWARA, On the computational power of exact counting, unpublished manuscript, April 1990. [17] 17. M. OGIWARA, Generalized theorems on relationships among reducibility notions to certain complexity classes, Mathematical Systems Theory, 1984, 27, pp. 189-200. Zbl0813.68105 MR1264385 · Zbl 0813.68105 [18] 18. M. OGIWARA and L. A. HEMACHANDRA, A complexity theory for feasible closure properties, Journal of Computer and System Sciences, 1993, 46 (3), pp. 295-325. Zbl0798.68060 MR1228809 · Zbl 0798.68060 [19] 19. J. SIMON, On some central problems in computational complexity, PhD thesis, Cornell University, January 1975. [20] 20. J. TORÁN, Structural properties of the Counting Hierarchy, PhD thesis, Universitat Politècnica de Catalunya, January 1990. [21] 21. K. W. WAGNER, The complexity of combinatorial problems with succinct input representation, Acta Informatica, 1986, 23, pp. 325-356. Zbl0621.68032 MR853581 · Zbl 0621.68032 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.