×

A relationship between difference hierarchies and relativized polynomial hierarchies. (English) Zbl 0776.68043

It has been shown (Kadin, Chang) that if the difference hierarchy over NP (i.e. the hierarchy obtained by systematically closing NP under the Boolean operations) collapses to some level \(k\), then the polynomial-time hierarchy collapses too, where the collapse level depends, of course, on \(k\). It is this dependence which is exploited and strengthened in the paper paper: The collapse of the polynomial-time hierarchy occurs at level \((p^{\text{NP}}_{(k-1)-tt})^{\text{NP}}\).
Reviewer: U.Schöning (Ulm)

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Allender and L. A. Hemachandra. Lower bounds for the low hierarchy. Inproceedings of the 16th ICALP, pages 31-45. Lecture Notes in Computer Science, Volume 372. Springer-Verlag, Berlin, 1989.
[2] A. Amir, R. Beigel, and W. I. Gasarch. Some connections between bounded query classes and non-uniform complexity. InProceedings of the 5th Annual Conference on Structure in Complexity Theory, pages 232-243. IEEE Computer Society Press, New York, July 1990. · Zbl 1058.68056
[3] A. Amir and W. I. Gasarch. Polynomial terse sets.Inform. and Comput. 77:37-56, April 1988. · Zbl 0646.68049
[4] J. L. Balcázar, R. V. Book, and U. Schöning. Sparse sets, lowness and highness.SIAM J. Comput.,15(3):739-747, August 1986. · Zbl 0621.68033
[5] R. Beigel. Bounded queries to SAT and the Boolean hierarchy.Theoret. Comput. Sci.,84(2): 199-223, July 1991. · Zbl 0739.68035
[6] R. Beigel, N. Reingold, and D. Spielman. PP is closed under intersection. To appear inJ. Comput. System Sci. An earlier version appeared inProceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 1-9. ACM Press, New York, May 1991. · Zbl 0827.68040
[7] A. Bertoni, D. Bruschi, D. Joseph, M. Sitharam, and P. Young. Generalized Boolean hierarchies and Boolean hierarchies over RP. InProceedings of the 7th Conference on Fundamentals of Computation Theory, pages 35-46. Lecture Notes in Computer Science, Volume 380. Springer-Verlag, Berlin, 1989. · Zbl 0756.68037
[8] J. Cai. On Some Most Probable Separations of Complexity Classes. Ph.D. thesis, Cornell University, Ithaca, NY, 1986.
[9] J. Cai, T. Gundermann, J. Hartmanis, L. A. Hemachandra, V. Sewelson, K. W. Wagner, and G. Wechsung. The Boolean hierarchy, I: structural properties.SIAM J. Comput.,17(6): 1232-1252, December 1988. · Zbl 0676.68011
[10] J. Cai and L. A. Hemachandra. The Boolean hierarchy: hardware over NP. InStructure in Complexity Theory, pages 105-124. Lecture Notes in Computer Science, Volume 223. Springer-Verlag, Berlin, June 1986.
[11] R. Chang and J. Kadin. The Boolean hierarchy and the polynomial hierarchy: a closer connection. InProceedings of the 5th Annual Conference on Structure in Complexity Theory, pages 169-178. IEEE Computer Society Press, New York, July 1990. · Zbl 0844.68048
[12] R. Chang and J. Kadin. On computing Boolean connectives of characteristic functions. Technical Report TR 90-1118, Department of Computer Science, Cornell University, Ithaca, NY, May 1990. To appear inMath. Systems Theory. · Zbl 0827.68065
[13] L. Fortnow and N. Reingold. PP is closed under truth-table reductions. InProceedings of the 6th Annual Conference on Structure in Complexity Theory, pages 13-15. IEEE Computer Society Press, New York, June 1991. · Zbl 0851.68029
[14] F. Green. On the power of deterministic reductions to C_P. To appear inMath. Systems Theory. · Zbl 0776.68045
[15] T. Gundermann, N. Nasser, and G. Wechsung. A survey of counting classes. InProceedings of the 5th Annual Conference on Structure in Complexity Theory, pages 140-153. IEEE Computer Society Press, New York, July 1990.
[16] J. Kadin. The polynomial time hierarchy collapses if the Boolean hierarchy collapses.SIAM J. Comput.,17(6): 1263-1282, December 1988. · Zbl 0664.03031
[17] J. Köbler, U. Scheming, and K. W. Wagner. The difference and truth-table hierarchies for NP.RAIRO Theoret. Inform. Appl.,21:419-435, 1987. · Zbl 0642.03024
[18] R. E. Ladner, N. A. Lynch, and A. L. Selman. A comparison of polynomial time reducibilities.Theoret. Comput. Sci.,1:103-123, 1975. · Zbl 0321.68039
[19] M. Ogiwara. On the computational power of exact counting. Unpublished manuscript, April 1990.
[20] U. Schöming.Complexity and Structure. Lecture Notes in Computer Science, Volume 211. Springer-Verlag, Berlin, 1985.
[21] M. Sitharam. Generalized Bounded Query Hierarchies. Ph.D. thesis, University of Wisconsin-Madison, 1990. · Zbl 0731.03024
[22] J. Torán. Complexity classes defined by counting quantifiers.J. Assoc. Comput. Mach.,38(3): 753-774, July 1991. · Zbl 0799.68080
[23] K. W. Wagner. The complexity of combinatorial problems with succinct input representation.Acta Inform.,23:325-356, 1986. · Zbl 0621.68032
[24] K. Wagner. Bounded query computations. InProceedings of the 3rd Structure in Complexity Theory Conference, pages 260-277, June 1988.
[25] K. W. Wagner. Number-of-query hierarchies. Technical Report 4, Institut fur Mathematik, Universitat Augsburg, 1989.
[26] K. W. Wagner. Bounded query classes.SIAM J. Comput.,19(5):833-846, October 1990. · Zbl 0711.68047
[27] G. Wechsung and K. Wagner. On the Boolean closure of NP. InProceedings of the 1985 International Conference on Fundamentals of Computation Theory, pages 485-493. Lecture Notes in Computer Science, Volume 199. Springer-Verlag, Berlin, 1985.
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.