PSPACE

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

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

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

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

\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PH} \subseteq \mbox{PSPACE}
\mbox{PSPACE} \subseteq \mbox{EXPTIME} \subseteq \mbox{EXPSPACE}
\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}

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

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