PSPACE

Oversikt over forholda mellom kompleksitetsklassene

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.

${\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}}$

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

• 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.