PSPACE

I matematikk og informatikk er PSPACE ei kompleksitetsklasse. Ho kan definerast som mengda av alle problem som kan løysast av ei turingmaskin med ei polynomiell mengde plass. 

 Relasjonar til andre kompleksitetsklasser 
Følgjande relasjonar er kjende mellom PSPACE og andre kompleksitetsklasser.  Merk at ⊊ ikkje er det same som ⊈. ⊊ er ekte-delmengde relasjonen. ⊆ er delmengderelasjonen.

Innehalde i PSPACE har ein òg PSPACE-komplette problem som er dei hardaste problema i PSPACE. Dei er definerte som ved andre kompleksitetsklasser.

 Eigenskapar 
PSPACE er lukka under operasjonane union, komplement og kleenestjerne.

Ein annan interessant eigenskap er at komplementet av PSPACE er lik PSPACE sjølv. Med andre ord er co-PSPACE = PSPACE.

 Litteratur 

 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), ss. 281–294.
Kategori:Kompleksitetsteori