HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is NL closed under complemenrt?

Submitted by: @import:stackexchange-cs··
0
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.