Paper Info
Title
Closure under Complementation of Logspace Complexity Classes - A Survey
Abstract
In this article we chronologically survey the closure under complementation results for several logspace-bounded complexity classes, namely the early collapses of the logspace alternation and oracle hierarchies, and the closure under complementation for NL, LOGCFL, and SL. The presentation of the proofs follows a uniform approach based on exact counting.
Year
DOI
Venue
1997
10.1007/BFb0052085
Foundations of Computer Science: Potential - Theory - Cognition
Keywords
Field
DocType
logspace complexity classes,complexity class
Complexity class,Discrete mathematics,Combinatorics,LOGCFL,Computer science,Oracle,Finite-state machine,Mathematical proof,Turing machine,Hierarchy,Alternation (linguistics)
Conference
ISBN
Citations 
PageRank 
3-540-63746-X
0
0.34
References 
Authors
34
1
Name
Order
Citations
PageRank
Birgit Jenner124714.47