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

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

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

Приклади:

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

NL-повні задачі

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

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

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

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

Теорема:

$(A\leq _{L}B)\land (B\in L)\Rightarrow A\in L$

Наслідок:

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

Твердження:

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

Наслідок:

$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»