Класс NL

Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием O(log n) дополнительной памяти для входа длинной n. Класс NL является обобщением класса L.

Используя определение NSPACE можно формализовать определение: NL = NSPACE(log n).

Соотношения между классами

Класс NL является подмножеством класса P, так как ...

Естественно назвать множество языков, дополнение до которых принадлежит NL, классом co-NL. Теорема Иммермана гласит, что классы NL и co-NL совпадают.

Вопросы о равенстве класса NL классам L и P открыты.