Класс NL
Версия от 15:14, 8 апреля 2010; Ulyantsev (обсуждение | вклад)
Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием O(log n) дополнительной памяти для входа длинной n. Класс NL является обобщением класса L.
Используя определение NSPACE можно формализовать определение: NL = NSPACE(log n).
Естественно назвать множество языков, дополнение до которых принадлежит NL, классом co-NL. Теорема Иммермана гласит, что классы NL и co-NL совпадают.
