PSPACE

From Wikipedia, the free encyclopedia

PSPACE

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.

Thumb
Oversikt over forholda mellom kompleksitetsklassene

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.

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

Autoritetsdata
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.