Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n.
Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n.
Примеры:
Преобразователь, требующий логарифмической памяти — машина Тьюринга с тремя лентами: входной, доступной только на чтение, выходной, доступной только на запись и рабочей лентой, на которой может использоваться не более O(log(n)) ячеек.
Функция, вычисляемая таким преобразователем называется функцией, вычисляемой с логарифмической памятью.
Задача A логарифмически по памяти сводится к задаче B, если есть логарифмическая по памяти функция, при помощи которой задача А сводится к задаче В. Обозначается
Язык называется NL-полным если он принадлежит NL и любой язык из NL сводится к нему логарифмически по памяти.
Теорема:
Следствие:
Утверждение:
Следствие:
Класс coNL — языки, дополнения до которых лежат в NL.
Теорема Иммермана:
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .