Ψ Die Informatikseite

Menü

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.