Content deleted Content added
No edit summary Tag: possible vandalism |
m Reverted edits by 71.191.69.66 (talk) to last version by Woohookitty |
||
Line 15:
Some of the most surprising complexity results shown to date showed that the complexity classes [[NL (complexity)|NL]] and [[SL (complexity)|SL]] are in fact closed under complement, whereas before it was widely believed they were not (see [[Immerman-Szelepcsényi theorem]]). The latter has become less surprising now that we know '''SL''' equals '''[[L (complexity)|L]]''', which is a deterministic class.
Every class which is [[low (complexity)|low]] for itself is closed under complement.
| |||