Papex

Open problem · Computer science · Open

L versus NL

Can every problem solvable by a nondeterministic machine with logarithmic memory also be solved deterministically with logarithmic memory?

Summary

NL contains problems such as deciding whether one node of a directed graph can reach another. L is contained in NL and NL in P, but it is not known whether either inclusion is an equality; in 1987 Immerman and Szelepcsényi independently showed that NL is closed under complement.

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 18 Nov 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing