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

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

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

Приклади:

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

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

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

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

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

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

Теорема:

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

Наслідок:

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

Твердження:

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

Наслідок:

$NL\subseteq P$.

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

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

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

NL = coNL

Література

• Шаблон:Cinderella Book
• Шаблон:Роджерс.Теорія рекурсивних функцій
• Michael Sipser: «Introduction to the Theory of Computation»