Σ2 SPACE(n) is closed under complement

摘要

One of the most important questions in the theory of computational complexity is whether nondeterministic spacebounded complexity classes are closed under complement. In the case of a linear space bound, this can be viewed as a second version of a famous question known as the LBA problem in Kuroda [3], and is a long-standing open question. Furthermore, since the concept called “alternation” was introduced in Chandra et al. [1] as a generalization of nondeterminism, many similar questions have arisen. A typical question is whether the linear space-bounded complexity class defined by alternating Turing machins allowing one alternation is closed under complement. We can view this as a third version of the LBA problem. In this paper, we answer this question; that is, we show that Σ2 SPACE(n) is closed under complement, where Σk SPACE(n) denotes a class of languages accepted by linear space-bounded alternating Turing machines whose initial state is existential and which make at most k − 1 alternations, for each k > 0. As an immediate consequence, the alternation linear-space hierarchy collapses to the second level, i.e., Σ2 SPACE(n) = Σk SPACE(n) for any k ≥ 2. By using the usual translational method, these results can be extended to any space bound greater than linear.