Классы L и NL

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

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

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

Примеры:

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

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»

Классы сложности алгоритмов

 

Cчитаются лёгкими	P • L • NL • AC • NC • P-complete • BQP • BPP • RP • ZPP
Предпологаются сложными	NP (co-NP • NP-complete • co-NP-complete ) • UP • #P (#P-complete ) • IP • PSPACE (PSPACE-complete) • R • PP • AM
Cчитаются сложными	EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH
Список алгоритмов