Closure under complementation of logspace complexity classes. A survey

DOI10.1007/BFB0052085MaRDI QIDQ4371019zbMATH OpenFDO

Authors Birgit Jenner

Publication date 7 January 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0052085

zbMATH Keywords

logspace-bounded complexity classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
• Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
• Two Applications of Inductive Counting for Complementation Problems
• \(\Sigma_ 2SPACE(n)\) is closed under complement
• Nondeterministic Space is Closed under Complementation

Cited in

(3)

• Nondeterministic Space is Closed under Complementation
• Two Applications of Inductive Counting for Complementation Problems
• A compendium of problems complete for symmetric logarithmic space

This page was built for publication: Closure under complementation of logspace complexity classes. A survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4371019)