Komplexität

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

• Eingabe: eine QBF F
• Frage: ist val(F) = 1

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!