PSPACE

Frå Wikipedia – det frie oppslagsverket
Hopp til navigering Hopp til søk
Oversyn over tilhøva mellom kompleksitetsklassene

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.

Relasjonar til andre kompleksitetsklasser[endre | endre wikiteksten]

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.

Eigenskapar[endre | endre wikiteksten]

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.

Litteratur[endre | endre wikiteksten]

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