Перегляд вихідного коду сторінки Клас складності PSPACE

'''PSPACE''' ({{lang-en|Polynomial Space}}&nbsp;— поліноміальне місце)&nbsp;— клас задач, які розв'язні на [[Машина Тюрінга|машині Тюрінга]] з використанням поліноміального запасу пам'яті.

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

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

== Зв'язки між класами ==
[[Файл:Complexity subsets pspace.svg|300px|thumb|right|Відношення вкладення між класами складності]]
Відомі такі зв'язки між PSPACE та класами [[Класи складності L і NL|NL]], [[Клас складності P|P]], [[Клас складності NP|NP]], [[Клас складності PH|PH]], [[EXPTIME]], EXPSPACE:
: <math>\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PH} \subseteq \mbox{PSPACE}</math>
: <math>\mbox{PSPACE} \subseteq \mbox{EXPTIME} \subseteq \mbox{EXPSPACE}</math>
: <math>\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}</math>

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

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

== Література ==
* {{Cinderella Book}}
* {{Роджерс.Теорія рекурсивних функцій}}
* {{cite book | first = Michael | last = Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url-access = registration | url = https://archive.org/details/introductiontoth00sips }} Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp.&nbsp;281–294.
* {{cite book| first=Christos | last=Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1}} Chapter 19: Polynomial space, pp.&nbsp;455–490.

{{Класи складності}}
{{-}}{{Comp-sci-stub}}
{{портали|Програмування|Інформаційні технології}}

[[Категорія:Класи складності]]
[[Категорія:Теорія алгоритмів]]