3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

This is known as the Immerman–Szelepcsényi theorem, and the technique used to proving it is called inductive counting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.