Vis kilden til PSPACE

[[Fil:Complexity_subsets_pspace.svg|thumb|Oversikt over forholda mellom [[kompleksitetsklasse]]ne]]
I [[matematikk]] og [[informatikk]] er '''PSPACE''' ei [[kompleksitetsklasse]]. Den kan defineres som [[Mengde|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.

<math>\begin{array}{l}
\mathsf{NL \subseteq P \subseteq NP \subseteq PH \subseteq PSPACE}\\
\mathsf{PSPACE \subseteq EXPTIME \subseteq EXPSPACE}\\
\mathsf{NL \subsetneq PSPACE \subsetneq EXPSPACE}\\
\mathsf{P\subsetneq EXPTIME}\end{array}</math>

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

== Egenskaper ==
PSPACE er lukka under operasjonene [[Union (mengdelære)|union]], [[Komplement (mengdelære)|komplement]] og [[kleenestjerne]].

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

== Litteratur ==
* {{cite book|authorlink=Michael Sipser|first=Michael|last=Sipser|year=1997|title=Introduction to the Theory of Computation|url=https://archive.org/details/introductiontoth00sips|publisher=PWS Publishing|isbn=0-534-94728-X}} Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), ss.&nbsp;281–294.

{{Autoritetsdata}}

[[Kategori:Kompleksitetsteori]]