Komplexität

Dieses Problem QBF-SAT ist PSPACE-vollständig:

Bemerkung: QBF $ \in$ PSPACE (alle Belegungen durchprobieren).

Aufgabe: es ist ein (Polynomialzeit-)Verfahren anzugeben, das zu jeder polynomiell platzbeschränkten Maschine M und Eingabewort w eine QBF F konstruiert, so daß w$ \to_{M}^{*}$ OK $ \iff$ $ \models$ F.

Problem: F darf nur polynomiell groß sein, die Rechnungen von M können aber exponentiell lang sein!



2009-06-22