Класи складності L і NL

Клас мов L — множина мов, розв'язних на детермінованій машині Тюрінга з використанням ${\displaystyle O(\log (n))}$ додаткової пам'яті для входу довжиною n.

Клас мов NL — множина мов, розв'язних на недетермінованій машині Тюрінга з використанням ${\displaystyle O(\log (n))}$ додаткової пам'яті для входу довжиною n.

Приклади:

• ${\displaystyle \{0^k{1}^k:k\ge 0\}\in L}$
• Нехай мова ${\displaystyle PATH=\{(G,s,t):G}$ — орієнтований граф, у якому є шлях від ${\displaystyle s}$ до ${\displaystyle t}$${\displaystyle \}}$, тоді ${\displaystyle PATH\in NL}$

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

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

Задача A логарифмічно за пам'яттю зводиться до задачі B, якщо є логарифмічна за пам'яттю функція, за допомогою якої задача A зводитися до задачі B. Позначають ${\displaystyle A{\le }_{L}B}$.

Мову називають NL-повною, якщо вона належить NL і будь-яка мова з NL зводиться до неї логарифмічно за пам'яттю.

Теорема:

${\displaystyle (A{\le }_{L}B)\wedge (B\in L)\Rightarrow A\in L}$

Наслідок:

Якщо NL-повна мова належить L, то L = NL

Твердження:

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

Наслідок:

${\displaystyle NL\subseteq P}$.

Клас coNL — мови, доповнення до яких лежать у NL.

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

NL = coNL

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (англ.) (вид. 2nd). Addison–Wesley. с. 521. Посилання на друге видання книги.
• Роджерс Х.. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
• Michael Sipser: «Introduction to the Theory of Computation»