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

DOI10.1016/0022-0000(87)90009-2zbMath0654.68053OpenAlexW1968785579MaRDI QIDQ1108795

Seinosuke Toda

Publication date: 1987

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(87)90009-2

zbMATH Keywords

alternating Turing machinescollapsing of complexity hierarchies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) ⋮ On the power of alternation on reversal-bounded alternating Turing machines with a restriction ⋮ A hierarchy that does not collapse : alternations in low level space ⋮ The strong exponential hierarchy collapses ⋮ Sublogarithmic $\sum _2$-space is not closed under complement and other separation results

Cites Work

• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy
• Alternation
• Classes of languages and linear-bounded automata
• Unnamed Item