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