×

The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\). (English) Zbl 0668.68055

It is shown that the second level of the logarithmic space hierarchy is closed under complementation, i.e., this hierarchy “collapses” to its second level. The result is proved by considering the Hausdorff closure of NL, and also the Boolean NL and NP hierarchy.
A more recent result by Immerman shows that the results reported in the present paper are not the strongest possible ones: Actually, NL is closed under complementation, i.e. the logarithmic alternation hierarchy collapses to its first level.
Reviewer: U.Schöning

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cai, J.; Hemachandra, L., The Boolean hierarchy: Hardware over NP, (Proceedings, Conf. Structure in Complexity Theory, Univ. of California, Berkeley. Proceedings, Conf. Structure in Complexity Theory, Univ. of California, Berkeley, Lect. Notes in Comput. Sci., Vol. 223 (1986), Springer-Verlag: Springer-Verlag New York/Berlin), 105-124 · Zbl 0611.68018
[2] Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. Assoc. Comput. Mach., 28, No. 1, 114-133 (1981) · Zbl 0473.68043
[3] Cook, S. A., The complexity of theorem proving procedures, (Proceedings, Third Annual ACM Symposium on the Theory of Computing (1971)), 151-158 · Zbl 0363.68125
[4] Goldschlager, L., The monotone and planar circuit value problems are LOG space complete for P, SIGACT News, 9, No. 35, 25-29 (1977) · Zbl 0356.94042
[5] Hopcroft, J.; Ullman, J., (Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0426.68001
[6] Immerman, N., (Nondeterministic Space Is Closed under Complement (1987), Yale University), July 1987
[7] Jenner, B., Die deterministische polynomielle Hierarchie-Ein polynomielles Analogon der Logarithmischen Alternierungshierarchie, (Diploma thesis (1987), University of Hamburg)
[8] Jenner, B.; Kirsig, B., Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata, (Proceedings, 5th STACS. Proceedings, 5th STACS, Lect. Notes in Comput. Sci., Vol. 294 (1988), Springer-Verlag: Springer-Verlag New York/Berlin), 118-125 · Zbl 0644.68056
[9] Jones, N. D., Reducibility among combinatorial problems in log \(n\) space, (Proceedings, 7th Annual Princeton Conf. on Information Sciences and Systems (1973)), 547-551
[10] Kadin, J., The polynomial hierarchy collapses if the Boolean hierarchy collapses (1987), manuscript · Zbl 0664.03031
[11] Kirsig, B., Logarithmic Hausdorff reductions (1986), submitted for publication
[12] Köbler, J.; Schöning, U.; Wagner, K. W., The difference and truth-table hierarchies for NP (1985), manuscript
[13] Ladner, R. E.; Lynch, N., Relativization of questions about log space computability, Math. Systems Theory, 10, 19-32 (1976) · Zbl 0341.68036
[14] Ladner, R. E.; Lynch, N.; Selman, A., A comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, 103-123 (1975) · Zbl 0321.68039
[15] Lange, K.-J., Two characterizations of the logarithmic alternation hierarchy, (Proceedings, 12th Symp. of Math. Foundations of Comput. Science. Proceedings, 12th Symp. of Math. Foundations of Comput. Science, Lect. Notes in Comput. Sci., Vol. 233 (1986), Springer-Verlag: Springer-Verlag New York/Berlin), 518-526 · Zbl 0616.68050
[16] Lange, K.-J.; Jenner, B.; Kirsig, B., The logarithmic alternation hierarchy collapses: \(A Σ_2^L = A Π_2^L\), (Proceedings, 14th ICALP, Karlsruhe. Proceedings, 14th ICALP, Karlsruhe, Lect. Notes in Comput. Sci., Vol. 267 (1987), Springer-Verlag: Springer-Verlag New York/Berlin), 531-541 · Zbl 0629.68051
[17] Meyer, A.; Stockmeyer, L., The equivalence problem for regular expressions with squaring requires exponential space, (Proceedings, 13th Annual IEEE Symp. on Switching and Automata Theory 1972 (1972)), 125-129
[18] Papadimitriou, C. H.; Yannakakis, M., The complexity of facets (and some facets of complexity), J. Comput. System Sci., 28, 244-259 (1984) · Zbl 0571.68028
[19] Rosier, L. E.; Yen, H., Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines, (Proceedings, 3rd STACS. Proceedings, 3rd STACS, Lect. Notes in Comput. Sci., Vol. 210 (1986), Springer-Verlag: Springer-Verlag New York/Berlin), 306-320 · Zbl 0615.68041
[20] Ruzzo, W.; Simon, J.; Tompa, M., Space-bounded hierarchies and probabilistic computations, J. Comput. System Sci., 28, 216-230 (1984) · Zbl 0573.68021
[21] Savitch, W., Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 4, 177-192 (1970) · Zbl 0188.33502
[22] Schöning, U.; Wagner, K. W., Collapsing oracle hierarchies, census functions and logarithmically many queries, (Report 140 (1987), Universität Augsburg) · Zbl 0648.68065
[23] Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1976) · Zbl 0353.02024
[24] Szelepscényi, R., The method of forcing for nondeterministic automata, Bull. European Associ. Theoret. Comput. Sci., 33, 96-100 (1987) · Zbl 0664.68082
[25] Toda, S., \(Σ_2\) SPACE \((n)\) is closed under complement, J. Comput. System Sci., 35, No. 2, 145-152 (1987) · Zbl 0654.68053
[26] Wagner, K. W., More complicated questions about maxima and minima, and some closures of NP, report (1986), University of Passau · Zbl 0629.68049
[27] Wagner, K. W., The complexity of combinatorial problems with succint input representation, Acta Inform., 23, No. 3, 325-356 (1986) · Zbl 0621.68032
[28] Wechsung, G., On the Boolean closure of NP, (Proceedings, FCT Conf.. Proceedings, FCT Conf., Lect. Notes in Comput. Sci., Vol. 199 (1985), Springer-Verlag: Springer-Verlag New York/Berlin), 485-493 · Zbl 0581.68043
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.