PSPACE

I matematikk og informatikk er PSPACE ei kompleksitetsklasse. Den kan defineres som mengda av alle problemer som kan løses av ei turingmaskin med en polynomiell mengde plass.

 Relasjoner til andre kompleksitetsklasser 
Følgende relasjoner er kjente mellom PSPACE og andre kompleksitetsklasser.  Merk at ⊊ ikke er det samme som ⊈. ⊊ er ekte delmengde relasjonen. ⊆ er delmengderelasjonen.

Inneholdt i PSPACE har man også PSPACE-komplette problemer som er de hardeste problemene i PSPACE. De er definert som ved andre kompleksitetsklasser.

 Egenskaper 
PSPACE er lukka under operasjonene union, komplement og kleenestjerne.

En annen interessant egenskap er at komplementet av PSPACE er lik PSPACE selv. Med andre ord er co-PSPACE = PSPACE.

 Litteratur 
  Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), ss. 281–294.

Kategori:Kompleksitetsteori