← All problems

L versus NL

Let LL contain the decision problems solvable by deterministic Turing machines using O(logn)O(\log n) work space, and let NLNL allow nondeterministic machines under the same space bound.

Is L=NLL = NL?

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li