PSPACE

Oversyn over tilhøva mellom kompleksitetsklassene

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.

$\begin{array}{c}𝖭𝖫\mathsf{\subseteq }𝖯\mathsf{\subseteq }𝖭𝖯\mathsf{\subseteq }𝖯𝖧\mathsf{\subseteq }𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖯𝖲𝖯𝖠𝖢𝖤\mathsf{\subseteq }𝖤𝖷𝖯𝖳𝖨𝖬𝖤\mathsf{\subseteq }𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖭𝖫\mathsf{⊊}𝖯𝖲𝖯𝖠𝖢𝖤\mathsf{⊊}𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖯\mathsf{⊊}𝖤𝖷𝖯𝖳𝖨𝖬𝖤\end{array}$

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.