From Wikipedia, the free encyclopedia
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.
Følgjande relasjonar er kjende mellom PSPACE og andre kompleksitetsklasser. Merk at ⊊ ikkje er det same som ⊈. ⊊ er ekte-delmengde relasjonen. ⊆ er delmengderelasjonen.
Innehalde i PSPACE har ein òg PSPACE-komplette problem som er dei hardaste problema i PSPACE. Dei er definerte som ved andre kompleksitetsklasser.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.