\(\Sigma_ 2SPACE(n)\) is closed under complement (Q1108795)

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 \textit{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.