Nächste Seite: Zusammenfassung Aufwärts: NPC Beweise Vorherige Seite: coNP   Inhalt

PSPACE-Vollständigkeit

Definition ähnlich der NP-Vollständigkeit:

• Das Problem muß in PSPACE liegen.
• Alle anderen in PSPACE liegenden Probleme müssen polynomiell auf dieses Problem reduzierbar sein.

---