_ 2SPACE(n) is closed under complement

DOI10.1016/0022-0000(87)90009-2zbMATH Open0654.68053OpenAlexW1968785579MaRDI QIDQ1108795FDOQ1108795

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

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

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)

Cites Work

• Alternation
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy
• Title not available (Why is that?)
• Classes of languages and linear-bounded automata

Cited In (8)

• 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
• Title not available (Why is that?)
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• Nondeterministic Space is Closed under Complementation
• Title not available (Why is that?)

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)