EXPSPACE-Vollständigkeit

Einfache Sprache

EXPSPACE-vollständig sind die Probleme die gleichzeitig zu Klasse EXPSPACE und EXPSPACE-schwer gehören. Also Probleme aus EXPSPACE auf welche jedes andere Problem aus EXPSPACE durch Polynomialzeitreduktion reduziert werden kann.

Def. EXPSPACE-Vollständigkeit

Eine Sprache $B_0$ heißt EXPSPACE-vollständig g.d.w. $B_0\in \mathbf{EXPSPACE}$ und $\forall B\in \mathbf{EXPSPACE}$ gilt: $B\leq_\mathrm{p} B_0$ .

Sätze

• SATZ EQ-REXP ist EXPSPACE-vollständig