PSPACE

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk
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[rediger | rediger kilde]

Følgende relasjoner er kjente mellom PSPACE og andre kompleksitetsklasser. Merk at ⊊ ikke er det samme som ⊈. ⊊ er ekte delmengde relasjonen. ⊆ er delmengderelasjonen.

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

Egenskaper[rediger | rediger kilde]

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[rediger | rediger kilde]

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