Классы L и NL
Материал из Википедии — свободной encyclopedia
Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n.
- Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется nl.
Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n.
Примеры:
- Пусть язык
— ориентированный граф в котором есть путь от s до t
, тогда