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

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

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

Приклади:

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

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

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

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

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

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

Теорема:

${\displaystyle (A\leq _{L}B)\land (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»