patternMinor
Is NL closed under complemenrt?
Viewed 0 times
complemenrtunderclosed
Problem
I am trying to understand if NL is closed under complement or not. By NL i mean the non-deterministic-logspace complexity. I suppose that the answer is linked to the fact that we don't even know if L = NL so scientifically speaking we cannot determinate if NL is closed or not on complement, for now. I've searched on the internet and wikipedia says that NL is closed on this operation but there is no demostration on that.
Solution
This is known as the Immerman–Szelepcsényi theorem, and the technique used to proving it is called inductive counting.
Context
StackExchange Computer Science Q#148212, answer score: 3
Revisions (0)
No revisions yet.