PSPACE (англ. Polynomial Space — поліноміальне місце) — клас задач, які розв'язні на машині Тюрінга з використанням поліноміального запасу пам'яті.
Формальне означення
Позначимо як SPACE(t(n)) множину задач, які розв'язні на машині Тюрінга з використанням запасу пам'яті O(t(n)) для деякої функції t від входу обсягом n. Тоді можна визначити PSPACE як , де PSPACE — строга надмножина множини контекстно-залежних формальних мов.
Якщо замість детермінованої машини Тюрінга взяти недетерміновану, то це не додасть задач до класу PSPACE. За теоремою Севіча, NPSPACE еквівалентний PSPACE, оскільки детермінована МТ може змоделювати роботу недетермінованої МТ без використання додаткової пам'яті, записуючи варіанти (можливо експоненційну кількість) по черзі на те саме місце.
Зв'язки між класами
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODJMelpsTDBOdmJYQnNaWGhwZEhsZmMzVmljMlYwYzE5d2MzQmhZMlV1YzNabkx6TXdNSEI0TFVOdmJYQnNaWGhwZEhsZmMzVmljMlYwYzE5d2MzQmhZMlV1YzNabkxuQnVadz09LnBuZw==.png)
Відомі такі зв'язки між PSPACE та класами NL, P, NP, PH, EXPTIME, EXPSPACE:
Відомо, що в першому і другому рядках наведених відношень між класами, принаймні одне відношення вкладення має бути строгим, але невідомо, котре. Досить імовірно, що всі ці відношення є строгими. Для обох відношень вкладення третього рядка точно відомо, що вони строгі. Перше випливає з прямої діагоналізації ([en]) і факту PSPACE = NPSPACE. Друге випливає з теореми про ієрархію місця.
Найважчі задачі класу PSPACE — PSPACE-повні задачі.
Література
- Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
- Мир, 1972. — 416 с. . Теория рекурсивных функций и эффективная вычислимость. — М. : (рос.)
- Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN . Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.
- Papadimitriou, Christos (1993). Computational Complexity (вид. 1st). Addison Wesley. ISBN . Chapter 19: Polynomial space, pp. 455–490.
![]() | Це незавершена стаття з інформатики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
PSPACE angl Polynomial Space polinomialne misce klas zadach yaki rozv yazni na mashini Tyuringa z vikoristannyam polinomialnogo zapasu pam yati Formalne oznachennyaPoznachimo yak SPACE t n mnozhinu zadach yaki rozv yazni na mashini Tyuringa z vikoristannyam zapasu pam yati O t n dlya deyakoyi funkciyi t vid vhodu obsyagom n Todi mozhna viznachiti PSPACE yak PSPACE k N SPACE n k displaystyle mbox PSPACE bigcup k in mathbb N mbox SPACE n k de PSPACE stroga nadmnozhina mnozhini kontekstno zalezhnih formalnih mov Yaksho zamist determinovanoyi mashini Tyuringa vzyati nedeterminovanu to ce ne dodast zadach do klasu PSPACE Za teoremoyu Sevicha NPSPACE ekvivalentnij PSPACE oskilki determinovana MT mozhe zmodelyuvati robotu nedeterminovanoyi MT bez vikoristannya dodatkovoyi pam yati zapisuyuchi varianti mozhlivo eksponencijnu kilkist po cherzi na te same misce Zv yazki mizh klasamiVidnoshennya vkladennya mizh klasami skladnosti Vidomi taki zv yazki mizh PSPACE ta klasami NL P NP PH EXPTIME EXPSPACE NL P NP PH PSPACE displaystyle mbox NL subseteq mbox P subseteq mbox NP subseteq mbox PH subseteq mbox PSPACE PSPACE EXPTIME EXPSPACE displaystyle mbox PSPACE subseteq mbox EXPTIME subseteq mbox EXPSPACE NL PSPACE EXPSPACE displaystyle mbox NL subsetneq mbox PSPACE subsetneq mbox EXPSPACE Vidomo sho v pershomu i drugomu ryadkah navedenih vidnoshen mizh klasami prinajmni odne vidnoshennya vkladennya maye buti strogim ale nevidomo kotre Dosit imovirno sho vsi ci vidnoshennya ye strogimi Dlya oboh vidnoshen vkladennya tretogo ryadka tochno vidomo sho voni strogi Pershe viplivaye z pryamoyi diagonalizaciyi en i faktu PSPACE NPSPACE Druge viplivaye z teoremi pro iyerarhiyu miscya Najvazhchi zadachi klasu PSPACE PSPACE povni zadachi LiteraturaHopcroft John E Ullman Jeffrey D 2001 Vstup do teoriyi avtomativ mov i obchislen vid 2nd Addison Wesley s 521 angl inshi movi Teoriya rekursivnyh funkcij i effektivnaya vychislimost M Mir 1972 416 s ros 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 vid 1st Addison Wesley ISBN 0 201 53082 1 Chapter 19 Polynomial space pp 455 490 Ce nezavershena stattya z informatiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi