Hopp til innhold

PSPACE

Fra Wikipedia, den frie encyklopedi
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]
Autoritetsdata