_ 2SPACE(n) is closed under complement
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.
- Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
- Nondeterministic Space is Closed under Complementation
- Compactness of \(\mathcal{S}(n)\)-closed spaces
- N-closed subsets of nearly compact spaces
- S(n)-\(\theta\)-closed spaces
- scientific article; zbMATH DE number 1559485
- scientific article; zbMATH DE number 1515328
- \(\mu\)-\(S\)-closed spaces
- N-compactness and -closed sets
- n-H-closed spaces
- [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
- On the power of alternation on reversal-bounded alternating Turing machines with a restriction
- Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
- scientific article; zbMATH DE number 4080916 (Why is no real title available?)
- Nondeterministic Space is Closed under Complementation
- scientific article; zbMATH DE number 1332655 (Why is no real title available?)
- A hierarchy that does not collapse : alternations in low level space
- scientific article; zbMATH DE number 1101597 (Why is no real title available?)
- The strong exponential hierarchy collapses
This page was built for publication: \(\Sigma_ 2SPACE(n)\) is closed under complement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108795)
