PSPACE
Az elméleti számítógép-tudomány , különösen a komplexitás elmélet , PSPACE a bonyolultsági osztály a döntési problémák dönt a Turing-gép determinisztikus a tér polinom .
Formális meghatározás
Ha a determinisztikus Turing-gépek által eldöntött döntési problémák halmazát hívjuk meg egy bemenet nagyságú függvényteret használva , akkor a PSPACE-t formálisan definiáljuk :
TÉR(t(nem)){\ displaystyle {\ mbox {SPACE}} (t (n))}O(t(nem)){\ displaystyle O (t (n))}t{\ displaystyle t}nem{\ displaystyle n}
PSPACE=⋃k∈NEMTÉR(nemk) .{\ displaystyle {\ mbox {PSPACE}} = \ bigcup _ {k \ in \ mathbb {N}} {\ mbox {SPACE}} (n ^ {k}) \.}
Kapcsolatok más osztályokkal
A Savitch-tétel kimondja, hogy a PSPACE = NPSPACE, vagyis a polinom térben a determinisztikus és a nem determinisztikus gépek azonos kifejezéssel rendelkeznek. Az Immerman -Szelepcsényi-tétel szerint PSPACE = coNPSPACE. Shamir tétele az interaktív bizonyítási rendszerek összefüggésében azt is megadja , hogy IP = PSPACE. A PSPACE osztály megegyezik az AP-vel, a döntési problémák osztályával, amelyet egy váltakozó Turing-gép határoz meg polinomiális időben.
Amint az alábbi képen látható, a következő zárványokkal rendelkezünk: NL P NP PSPACE EXPTIME EXPSPACE .
⊆{\ displaystyle \ scriptstyle \ subseteq}⊆{\ displaystyle \ scriptstyle \ subseteq} ⊆{\ displaystyle \ scriptstyle \ subseteq}⊆{\ displaystyle \ scriptstyle \ subseteq} ⊆{\ displaystyle \ scriptstyle \ subseteq}
A térbeli hierarchia tétel szerint az NL és a PSPACE különbözik egymástól. A PSPACE tartalmazza a polinomiális hierarchiát : PH PSPACE.
⊆{\ displaystyle \ subseteq}
PSPACE-teljes problémák
Az NP-teljességhez hasonlóan meghatározhatjuk a PSPACE-teljes problémák fogalmát. A probléma akkor nehéz PSPACE, ha a PSPACE minden problémája polinomiális idő alatt csökken. A probléma akkor teljes, ha PSPACE-ben van, és nehéz a PSPACE-ben.
Logikai számszerűsített képletek
A kvantált logikai képlet (QBF rövidítve a számszerűsített logikai képletnél ) egy olyan képlet, amelynek a kvantorai ( vagy ) és a logikai változók. Ha egy ilyen képlet zárt , akkor igaz vagy hamis.
Q1x1Q2x2...Qnemxnemφ(x1,x2,...,xnem){\ displaystyle Q_ {1} x_ {1} Q_ {2} x_ {2} ... Q_ {n} x_ {n} \ varphi (x_ {1}, x_ {2}, ..., x_ {n })}Qén{\ displaystyle Q_ {i}}∀{\ displaystyle \ forall}∃{\ displaystyle \ létezik}xén{\ displaystyle x_ {i}}
A QBF-SAT (egy számszerűsített logikai képlet kielégíthetősége) probléma, más néven TQBF (az igazi számszerűsített logikai képlet esetében ) a következő:
- Nevezés: zárt QBF képlet ;ψ{\ displaystyle \ psi}
- Kérdés: igaz?ψ{\ displaystyle \ psi}
A QBF-SAT probléma PSPACE-teljes.
Nyelvelmélet
Adott egy szabályos kifejezés , a probléma az, hogy ez generálja az összes lehetséges szavak PSPACE-teljes. Ez a szabályos kifejezés egyetemességének problémája.
Az is, hogy a k determinisztikus véges automaták nyelveinek metszéspontja üres-e, szintén teljes PSPACE.
Tervezés
A tervezés a klasszikus, amikor van-e műveletsort a cél elérése érdekében a kezdeti helyzet (kiinduló helyzet, cél és leírt cselekvések egy rövid beszédet STRIPS ) van PSPACE-teljes.
Játékok
Bizonyos játékok esetében az, hogy valamelyik játékosnak van-e nyerő stratégiája egy adott játékhelyzetből, PSPACE-teljes. Például a hex , noughts és cross vagy Othello egyes változatai rendelkeznek ezzel a tulajdonsággal. Általánosságban elmondható, hogy egyes szerzők úgy vélik, hogy a PSPACE egyik központi fogalma az a tény, hogy tökéletes információval képes meghatározni a kétjátékos játékok optimális stratégiáját. A kényszerlogika egy eszköz, amely bemutatja néhány ilyen játék PSPACE-keménységét.
Játékok grafikonokban
Az általánosított földrajzi játék PSPACE-teljes. Papadimitriou és Yannakakis rövidebb útvonal- problémákat határoztak meg, amelyekben az ügynöknek nincs teljes térképe a mozgásra; PSPACE-teljesek.
Logika
A kvantált logikai képlet kielégíthetőségi problémájához hasonlóan (lásd fent), az alábbi logikák elégedettségi problémái is teljesek:
A tulajdonság következő logikáját ellenőrző modell PSPACE-teljes:
- LTL;
-
CTL * ;
- elsőrendű logika .
Egyéb kérdések a PSPACE-ben
1999-ben W. Plandowski bebizonyította, hogy a szavak egyenletének elfogadhatósága a PSPACE-ben van, míg a NEXPTIME-ban csak egy felső határ ismert . A valós számok elméletében egzisztenciálisan számszerűsített elsőrendű képlet kielégíthetőségi problémája a PSPACE-ben található.
Bibliográfia
Külső linkek
Megjegyzések és hivatkozások
-
Walter Savitch , „ Kapcsolatok a nemdeterminisztikus és determinisztikus szalagkomplexumok között ”, Journal of Computer and System Sciences , vol. 4, n o 21972
-
Adi Shamir, „ IP = PSPACE ”, Journal of the ACM , vol. 39, n o 4,1992. október, P. 869-877 ( online olvasás )
-
-
HB, III Hunt : „A nyelvek időbeli és szalagos összetettségéről. I ” , a számítástechnika elméletének ötödik éves ACM szimpóziumában (Austin, Tex., 1973) ,
1973( online olvasható ) , p. 10-19.
-
D. Kozen , „A természetes bizonyítási rendszerek alsó határai ”, 18. éves szimpózium a számítástechnika alapjairól (sfcs 1977) ,1977. október, P. 254–266 ( DOI 10.1109 / SFCS.1977.16 , online olvasás , hozzáférés : 2019. július 8. ) :
„Def. 3.2.2 és Lemma 3.2.3, p. 261 "
-
(in) " A propositional STRIPS ütemterv számítási bonyolultsága " , Mesterséges intelligencia , vol. 69, n csont 1-2,1 st szeptember 1994, P. 165-204 ( ISSN 0004-3702 , DOI 10.1016 / 0004-3702 (94) 90081-7 , olvasható online , elérhető február 28, 2018 )
-
(in) Sanjeev Arora és Boaz Barak , számítási komplexitás: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , fej . 4.2.2 ("A PSPACE lényege: optimális stratégiák a játékhoz").
-
(in) Robert Aubrey Hearn , " játékok, rejtvények és számítás " , Massachusetts Institute of Technology (PhD) ,2016( online olvasás , konzultáció 2018. április 28-án )
-
Thomas J. Schaefer : „ Néhány kétszemélyes tökéletes információs játék komplexitásáról ”, Journal of Computer and System Sciences , vol. 16, n o 21 st április 1978, P. 185–225 ( ISSN 0022-0000 , DOI 10.1016 / 0022-0000 (78) 90045-4 , online olvasás , hozzáférés : 2019. július 10 )
-
(in) Christos H. Papadimitriou és Mihalis Yannakakis , "A legrövidebb utak térkép nélkül " , Automaták, nyelvek és programozás , Springer Berlin Heidelberg, olvassa el a Megjegyzések a számítástechnikában című cikket,1989, P. 610–620 ( ISBN 9783540462019 , DOI 10.1007 / bfb0035787 , online olvasás , hozzáférés : 2019. július 10. )
-
(en) Richard E. Ladner, A bizonyíthatóság számítási bonyolultsága a modális propozíciós logika rendszereiben , SIAM folyóirat a számítástechnikáról,1977( online olvasható ) , p. 467–480.
-
Wojciech Plandowski , „A szóegyenletek kielégíthetősége a konstansokkal a PSPACE-ben van ”, a 40. éves szimpózium a számítástechnika alapjairól , IEEE Computer Society, fOCS '99,1999, P. 495- ( ISBN 9780769504094 , olvasható online , elérhető június 24, 2019 )
-
John Canny , „ Néhány algebrai és geometriai számítás a PSPACE-ben ”, A számítástechnika elméletének huszadik éves ACM szimpóziumának anyagai, ACM, sTOC '88,1988, P. 460–467 ( ISBN 9780897912648 , DOI 10.1145 / 62212.62257 , online olvasás , hozzáférés : 2019. június 24. )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">