Классы L и NL

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется nl.

Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием  O(\log(n)) дополнительной памяти для входа длиной n.

Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием  O(\log(n)) дополнительной памяти для входа длиной n.

Примеры:

NL-полные задачи[править | править вики-текст]

Преобразователь, требующий логарифмической памяти — машина Тьюринга с тремя лентами: входной, доступной только на чтение, выходной, доступной только на запись и рабочей лентой, на которой может использоваться не более O(log(n)) ячеек.


Функция, вычисляемая таким преобразователем называется функцией, вычисляемой с логарифмической памятью.

Задача A логарифмически по памяти сводится к задаче B, если есть логарифмическая по памяти функция, при помощи которой задача А сводится к задаче В. Обозначается  A \le_L B

Язык называется NL-полным если он принадлежит NL и любой язык из NL сводится к нему логарифмически по памяти.

Теорема:

(A \le_L B) \and (B \in L) \Rightarrow    A \in L

Следствие:

Если NL-полный язык принадлежит L, то L = NL

Утверждение:

PATH — NL-полная задача.

Следствие:

 NL \subseteq P .

Теорема Иммермана[править | править вики-текст]

Класс coNL — языки, дополнения до которых лежат в NL.

Теорема Иммермана:

NL = coNL

Литература[править | править вики-текст]

  • Michael Sipser: «Introduction to the Theory of Computation»