Класс NL — различия между версиями
Ulyantsev (обсуждение | вклад) (Новая страница: «Класс языков '''NL''' — множество языков, разрешимых на недетерминированной машине Тьюринга …») |
Ulyantsev (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | Класс языков '''NL''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием ''O''(log ''n'') дополнительной памяти для входа длинной ''n''. | + | Класс языков '''NL''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием ''O''(log ''n'') дополнительной памяти для входа длинной ''n''. |
| + | |||
| + | Используя определение '''[[Класс NSPACE|NSPACE]]''' можно формализовать определение: NL = '''NSPACE'''(log ''n''). | ||
Версия 16:12, 7 апреля 2010
Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием O(log n) дополнительной памяти для входа длинной n.
Используя определение NSPACE можно формализовать определение: NL = NSPACE(log n).
