Классы L и NL

Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется nl.

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

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

Примеры:

• $\{0^k{1}^k:k\ge <!--\; \ge \; -->0\}\in <!--\; \in \; -->L$$\{0^{k}1^{k}:k\geq 0\}\in L$
• Пусть язык $PATH=\{(G,s,t):G$$PATH=\{(G,s,t):G$ — ориентированный граф в котором есть путь от s до t$\}$$\}$, тогда $PATH\in <!--\; \in \; -->NL$$PATH\in NL$

NL-полные задачиПравить

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

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

Задача A логарифмически по памяти сводится к задаче B, если есть логарифмическая по памяти функция, при помощи которой задача А сводится к задаче В. Обозначается $A{\le <!--\; \le \; -->}_{L}B$$A\leq _{L}B$ 

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

Теорема:

$(A{\le <!--\; \le \; -->}_{L}B)\wedge <!--\; \wedge \; -->(B\in <!--\; \in \; -->L)\Rightarrow <!--\; \Rightarrow \; -->A\in <!--\; \in \; -->L$$(A\leq _{L}B)\land (B\in L)\Rightarrow A\in L$ 

Следствие:

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

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

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

Следствие:

$NL\subseteq <!--\; \subseteq \; -->P$$NL\subseteq P$ .

Теорема ИммерманаПравить

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

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

NL = coNL

ЛитератураПравить

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