_ 2SPACE(n) is closed under complement

DOI10.1016/0022-0000(87)90009-2MaRDI QIDQ1108795zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• 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
• Publication:4507875
• \(\mu\)-\(S\)-closed spaces
• \(N\)-compactness and \(\theta\)-closed sets
• \(n\)-H-closed spaces

Cites work

• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Alternation
• Classes of languages and linear-bounded automata
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy

Cited in

(8)

• A hierarchy that does not collapse : alternations in low level space
• On the power of alternation on reversal-bounded alternating Turing machines with a restriction
• scientific article; zbMATH DE number 4080916 (Why is no real title available?)
• The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
• Nondeterministic Space is Closed under Complementation
• scientific article; zbMATH DE number 1332655 (Why is no real title available?)
• The strong exponential hierarchy collapses
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results

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)