\(\Sigma_ 2SPACE(n)\) is closed under complement. (English) Zbl 0654.68053

A number of results on the collapsing of complexity hierarchies have been obtained in recent years. This paper is concerned with the \(\Sigma_ k\)SPACE\((n)\)-hierarchy of languages accepted by linear space bounded alternating Turing machines. It is shown that the hierarchy collapses to \(\Sigma_ 2\)SPACE\((n)\) by proving that \(\Sigma_ k\)SPACE\((n)\supseteq \Pi_ k\)SPACE\((n).\)
However, since this paper was published, an improvement to this result has been obtained by Immerman, who has proved that \(N\)SPACE\((n)=\)co-\(N\)SPACE\((n)\). Since \(\Sigma_ 1\)SPACE\((n)=N\)SPACE\((n)\) we see that the hierarchy actually collapses to \(\Sigma_ 1\)SPACE\((n)=\Pi_ 1\)SPACE\((n)\). Details of this improved result, which has quite a short proof, can be found in the article by J. Hartmanis [The collapsing hierarchies - the structural complexity column, Bull. EATCS 33, 26-39 (1987)].
Although the author proves a much weaker result, it is interesting to note the use of census functions, (which tell us how many strings are shorter than a given integer). This technique has been used to prove a number of interesting results in complexity theory recently.
Reviewer: Ph.W.Grant


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


[1] Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. Assoc. Comput. Mach., 28, 114-133 (1981) · Zbl 0473.68043
[2] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[3] Kuroda, S. Y., Classes of languages and linear bounded automata, Inform. and Control, 7, 207-223 (1964) · Zbl 0199.04002
[4] Mahaney, S., Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis, J. Comput. System Sci., 25, 130-143 (1982) · Zbl 0493.68043
[5] Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1976) · Zbl 0353.02024
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.