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}{c}𝖭𝖫\mathsf{\subseteq }𝖯\mathsf{\subseteq }𝖭𝖯\mathsf{\subseteq }𝖯𝖧\mathsf{\subseteq }𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖯𝖲𝖯𝖠𝖢𝖤\mathsf{\subseteq }𝖤𝖷𝖯𝖳𝖨𝖬𝖤\mathsf{\subseteq }𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖭𝖫\mathsf{⊊}𝖯𝖲𝖯𝖠𝖢𝖤\mathsf{⊊}𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖯\mathsf{⊊}𝖤𝖷𝖯𝖳𝖨𝖬𝖤\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

• Mal:Cite book Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), ss. 281–294.