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