×

The strong exponential hierarchy collapses. (English) Zbl 0693.03022

It is shown that the so-called strong exponential hierarchy collapses. The strong exponential hierarchy is formally obtained by considering the sequence of complexity classes: NE, P(NE), NP(NE), NP(NP(NE)), etc. Here, NP resp. NE mean nondeterministic polynomial (resp. exponential) time. The “collapse” happens at the \(\Delta_ 2\) level, i.e. \(P(NE)=NP(NE)=... \). The result is proved by using census counting techniques and by making extensive use of nondeterminism.
Reviewer: U.Schöning

MSC:

03D15 Complexity of computation (including implicit computational complexity)
03D55 Hierarchies of computability and definability
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allender, E.; Watanabe, O., Kolmogorov complexity and the degrees of tally sets, (Proceedings, 3rd Structure in Complexity Theory Conference (June 1988), IEEE Computer Society Press: IEEE Computer Society Press New York), 102-111
[2] Beigel, R., Bounded Queries to SAT and the Boolean Hierarchy, (Technical Report TR-7 (June 1987), Johns Hopkins Department of Computer Science: Johns Hopkins Department of Computer Science Baltimore, MD) · Zbl 0739.68035
[3] Baker, T.; Gill, J.; Solovay, R., Relativizations of the P=?NP question, SIAM J. Comput., 4, No. 4, 431-442 (1975) · Zbl 0323.68033
[4] Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. Comput., 6, No. 2, 305-322 (1977) · Zbl 0356.68059
[5] Buss, S.; Hay, L., On truth-table reducibility to SAT and the difference hierarchy over NP, (Proceedings, 3rd Structure in Complexity Theory Conference (June 1988), IEEE Computer Society Press: IEEE Computer Society Press New York), 224-233
[6] Book, R.; Long, T.; Selman, A., Quantitative relativizations of complexity classes, SIAM J. Comput., 13, No. 3, 461-487 (1984) · Zbl 0599.03041
[7] Book, R.; Long, T.; Selman, A., Qualitative relativizations of complexity classes, J. Comput. System Sci., 30, 395-413 (1985) · Zbl 0569.03016
[8] Book, R., Bounded query machines: On NP and PSPACE, Theoret. Comput. Sci., 15, 27-39 (1981) · Zbl 0473.68039
[9] Cai, J.; Gundermann, T.; Hartmanis, J.; Hemachandra, L.; Sewelson, V.; Wagner, K.; Wechsung, G., The boolean hierarchy. II. Applications, SIAM J. Comput., 18, No. 1, 95-111 (1989) · Zbl 0676.68012
[10] Cai, J.; Gundermann, T.; Hartmanis, J.; Hemachandra, L.; Sewelson, V.; Wagner, K.; Wechsung, G., The boolean hierarchy. I. Structural properties, SIAM J. Comput., 17, No. 6, 1232-1252 (1988) · Zbl 0676.68011
[11] Chandra, A.; Kozen, D.; Stockmeyer, L., Alternation, J. Assoc. Comput. Mach., 26, No. 1 (1981) · Zbl 0473.68043
[12] Clote, P.; Takeuti, G., Exponential time and bounded arithmetic, (Proceedings, Ist Structure in Complexity Theory Conference. Proceedings, Ist Structure in Complexity Theory Conference, Lecture Notes in Computer Science, Vol. 223 (1986), Springer-Verlag: Springer-Verlag New York/Berlin), 125-143 · Zbl 0621.03026
[13] Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[14] Hartmanis, J., Solvable problems with conflicting relativizations, Bull. European Assoc. Theoret. Comput. Sci., 27, 40-49 (1985)
[15] Hemachandra, L., Can P and NP Manufacture Randomness?, (Technical Report TR86-795 (December 1986), Cornell Computer Science Department: Cornell Computer Science Department Ithaca, NY)
[16] Hemachandra, L., THE SKY IS FALLING: The Strong Exponential Hierarchy Collapses, (Technical Report TR86-777 (August 1986), Department of Computer Science, Cornell University: Department of Computer Science, Cornell University Ithaca, NY)
[17] Hemachandra, L., Counting in Structural Complexity Theory, (Ph.D. thesis (May 1987), Cornell University: Cornell University Ithaca, NY)
[18] Cornell Department of Computer Science Technical Report TR87-840.; Cornell Department of Computer Science Technical Report TR87-840.
[19] Hemachandra, L., The strong exponential hierarchy collapses, (19th ACM Symposium on Theory of Computing (May 1987)), 110-122
[20] Hemachandra, L., The strong exponential hierarchy collapses, (Proceedings, 2nd Structure in Complexity Theory Conference (June 1987), IEEE Computer Society Press: IEEE Computer Society Press New York), (Abstract) · Zbl 0693.03022
[21] Hartmanis, J.; Hemachandra, L., Complexity classes without machines: On complete languages for UP, Theoret. Comput. Sci., 58, 129-142 (1988) · Zbl 0655.68044
[22] Hartmanis, J.; Hemachandra, L., On sparse oracles separating feasible complexity classes, Inform. Process. Lett., 28, 291-295 (1988) · Zbl 0658.68055
[23] Hartmanis, J.; Immerman, N.; Sewelson, V., Sparse sets in NP-P: EXPTIME versus NEXPTIME, Inform. and Control, 65, Nos 2/3, 159-181 (1985) · Zbl 0586.68042
[24] Hartmanis, J.; Stearns, R., On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117, 285-306 (1965) · Zbl 0131.15404
[25] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[26] Hartmanis, J.; Yesha, Y., Computation times of NP sets of different densities, Theoret. Comput. Sci., 34, 17-32 (1984) · Zbl 0985.68515
[27] Immerman, N., Nondeterministic space is closed under complementation, (Proceedings, 3rd Structure in Complexity Theory Conference (June 1988), IEEE Computer Society Press: IEEE Computer Society Press New York), 112-115 · Zbl 0668.68056
[28] Kadin, J., Deterministic Polynomial Time with \(O\)(log \((n))\) Queries, (Technical Report TR-86-771 (August 1986), Cornell University: Cornell University Itaaca, NY)
[29] Kadin, J., \(P^{NP}[log_n]\) and sparse Turing-complete sets for NP, (Proceedings, 2nd Structure in Complexity Theory Conference (June 1987), IEEE Computer Society Press: IEEE Computer Society Press New York), 33-40
[30] J. Kilian, June 1987, personal communication.; J. Kilian, June 1987, personal communication.
[31] Köbler, J.; Schöning, U.; Wagner, K., The Difference and Truth-Table Hierarchies for NP, (Technical Report (July 1986), Fachberichte Informatik, EWH Rheinland-Pfalz, Koblenz: Fachberichte Informatik, EWH Rheinland-Pfalz, Koblenz West Germany) · Zbl 0642.03024
[32] Lange, K.; Jenner, B.; Kirsig, B., The logarithmic alternation hierarchy collapses: \( AΣ_2^L = AΠ_2^L \), (Automata, Languages, and Programming (ICALP 1987). Automata, Languages, and Programming (ICALP 1987), Lecture Notes in Computer Science (1987), Springer-Verlag: Springer-Verlag New York/Berlin)
[33] Ladner, R.; Lynch, N.; Selman, A., A comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, No. 2, 103-124 (1975) · Zbl 0321.68039
[34] Long, T., Erratum, 17, No. 3, 628 (1988) · Zbl 0652.68056
[35] Mahaney, S., Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis, J. Comput. System Sci., 25, No. 2, 130-143 (1982) · Zbl 0493.68043
[36] Papadimitriou, C.; Zachos, S., Two remarks on the power of counting, (Proceedings, 6th GI Conference on Theoretical Computer Science. Proceedings, 6th GI Conference on Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 145 (1983), Springer-Verlag: Springer-Verlag New York/Berlin), 269-276 · Zbl 0506.68039
[37] (Selman, A., Proceedings, 1st Structure in Complexity Theory Conference. Proceedings, 1st Structure in Complexity Theory Conference, Lecture Notes in Computer Science, Vol. 223 (June 1986), Springer-Verlag: Springer-Verlag New York/Berlin) · Zbl 0591.00015
[38] Sewelson, V., A Study of the Structure of NP, (Ph.D. thesis (August 1983), Cornell University: Cornell University Ithaca, NY)
[39] Cornell Department of Computer Science Technical Report No. 83-575.; Cornell Department of Computer Science Technical Report No. 83-575.
[40] Selman, A.; Mei-Rul, X.; Book, R., Positive relativizations of complexity classes, SIAM J. Comput., 12, 565-579 (1983) · Zbl 0551.68043
[41] Stockmeyer, L., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[42] Schöning, U.; Wagner, K., Collapsing oracle hierarchies, census functions, and logarithmically many queries, (STACS 1988: 5th Annual Symposium on Theoretical Aspects of Computer Science. STACS 1988: 5th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science (February 1988), Springer-Verlag: Springer-Verlag New York/Berlin) · Zbl 0648.68065
[43] Toda, S., \(Σ_2\) SPACE \([n]\) is closed under complement, J. Comput. System Sci., 35, 145-152 (1987) · Zbl 0654.68053
[44] Wagner, K., Bounded query computation, (Proceedings, 3rd Structure in Complexity Theory Conference (June 1988), IEEE Computer Society Press: IEEE Computer Society Press New York), 260-277
[45] O. Watanabe, May 1987, personal communication.; O. Watanabe, May 1987, personal communication.
[46] Yesha, Y., On certain polynomial-time truth-table reducibilities of complete sets to sparse sets, SIAM J. Comput., 12, No. 3, 411-425 (1983) · Zbl 0545.03023
[47] Zachos, S., Probabilistic quantifiers, adversaries, and complexity classes: An overview, (Proceedings, 1st Structure in Complexity Theory Conference (June 1986), IEEE Computer Society Press: IEEE Computer Society Press New York), 383-400 · Zbl 0632.03035
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.