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

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

Позначимо як SPACE(t(n)) множину задач, які розв'язні на машині Тюрінга з використанням запасу пам'яті O(t(n)) для деякої функції t від входу обсягом n. Тоді можна визначити PSPACE як  , де PSPACE — строга надмножина множини контекстно-залежних формальних мов.

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

Зв'язки між класами ред.

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

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

 
 
 

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

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

Література ред.

  • Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.
  • Papadimitriou, Christos (1993). Computational Complexity (вид. 1st). Addison Wesley. ISBN 0-201-53082-1.  Chapter 19: Polynomial space, pp. 455–490.