Клас складності PSPACE

PSPACE (Шаблон:Lang-en — поліноміальне місце) — клас задач, які розв'язні на машині Тюрінга з використанням поліноміального запасу пам'яті.

Формальне означення

Позначимо як SPACE(t(n)) множину задач, які розв'язні на машині Тюрінга з використанням запасу пам'яті O(t(n)) для деякої функції t від входу обсягом n. Тоді можна визначити PSPACE як $\text{PSPACE}=\bigcup _{k\in \mathbb{N}}\text{SPACE}(n^k)$, де PSPACE — строга надмножина множини контекстно-залежних формальних мов.

Якщо замість детермінованої машини Тюрінга взяти недетерміновану, то це не додасть задач до класу PSPACE. За теоремою Севіча, NPSPACE еквівалентний PSPACE, оскільки детермінована МТ може змоделювати роботу недетермінованої МТ без використання додаткової пам'яті, записуючи варіанти (можливо експоненційну кількість) по черзі на те саме місце.

Зв'язки між класами

Відношення вкладення між класами складності

Відомі такі зв'язки між PSPACE та класами NL, P, NP, PH, EXPTIME, EXPSPACE:

$\text{NL}\subseteq \text{P}\subseteq \text{NP}\subseteq \text{PH}\subseteq \text{PSPACE}$

$\text{PSPACE}\subseteq \text{EXPTIME}\subseteq \text{EXPSPACE}$

$\text{NL}⊊\text{PSPACE}⊊\text{EXPSPACE}$

Відомо, що в першому і другому рядках наведених відношень між класами, принаймні одне відношення вкладення має бути строгим, але невідомо, котре. Досить імовірно, що всі ці відношення є строгими. Для обох відношень вкладення третього рядка точно відомо, що вони строгі. Перше випливає з прямої діагоналізації (Шаблон:Нп) і факту PSPACE = NPSPACE. Друге випливає з теореми про ієрархію місця.

Найважчі задачі класу PSPACE — PSPACE-повні задачі.

Література

• Шаблон:Cinderella Book
• Шаблон:Роджерс.Теорія рекурсивних функцій
• Шаблон:Cite book Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.
• Шаблон:Cite book Chapter 19: Polynomial space, pp. 455–490.