PSPACE-Vollständigkeit
Einfache Sprache
PSPACE-vollständig sind die Probleme die gleichzeitig zu Klasse PSPACE und PSPACE-schwer gehören. Also Probleme aus PSPACE auf welche jedes andere Problem aus PSPACE durch Polynomialzeitreduktion reduziert werden kann.
Def. PSPACE-Vollständigkeit
Eine Sprache $B_0$ heißt PSPACE-vollständig g.d.w. $B_0\in \mathbf{PSPACE}$ und $\forall B\in \mathbf{PSPACE}$ gilt: $B\leq_\mathrm{p} B_0$ .
Bemerke: Wir nutzen in der Definition von PSPACE-Vollständigkeit Polynomialzeitreduktion und nicht Polynomialplatzreduktion aus einem gutem Grund. Die Reduktion muss “einfach” bzgl. des eigentlichen Problems sein, da sonst eine “einfache” Lösung für ein Problem $A$, durch die “schwere” Reduktion $p$ auf das Problem $B$, $B$ immer noch “schwer” sein lässt. Was den Sinn einer Reduktion wiederspricht.