Класс NL — различия между версиями
Ulyantsev (обсуждение | вклад) (→Соотношения между классами) |
м (rollbackEdits.php mass rollback) |
| (не показана 1 промежуточная версия 1 участника) | |
(нет различий)
| |
Текущая версия на 19:37, 4 сентября 2022
Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием O(log n) дополнительной памяти для входа длинной n.
Используя определение NSPACE можно формализовать определение: NL = NSPACE(O(log n)).
Соотношения между классами
Класс NL является обобщением класса L, в определении которого используется детерминированная машина Тьюринга.
Класс NL является подмножеством класса P, так как число конфигураций машины, использующей O(log n) памяти не превышает 2O(log n) = nO(1), а, следовательно, машина завершает свою работу за O(nС) времени.
Вопросы о равенстве класса NL классам L и P открыты.
Естественно назвать множество языков, дополнение до которых принадлежит NL, классом co-NL. Теорема Иммермана гласит, что классы NL и co-NL совпадают.
