Satz FORMULA-GAME ist PSPACE-vollständig
Einfache Sprache
Def. Satz FORMULA-GAME ist PSPACE-vollständig
Beweisidee: Wir zeigen das $\mathrm{FORMULA\text{-}GAME}$ PSPACE-vollständig ist indem wir die Parallelen zu TQBF zeigen. Denn eine Formel ist wahr genau dann wenn Spieler E eine Gewinnstrategie in dem Formelspiel für diese Formel hat.
Beweis: Die Formel $\phi = \exists x_1\forall x_2\exists x_3\ldots[\psi]$ ist wahr wenn es Wert für $x_1$ gibt so, dass für alle möglichen Werte für x_2 es einen Wert für $x_3$ gibt so, dass $\ldots$, dass $\phi$ wahr bzgl. der Belegung der Variablen ist. Ebenso hat Spieler E eine Gewinnstrategie in dem Formelspiel von $\phi$ wenn E $x_1$ einem Wert geben kann so, dass für alle möglichen Werte für $x_2$ E $x_3$ einem Wert geben kann so, dass $\ldots$, dass $\phi$ wahr ist bzgl. der gewählten Werte für die Variablen.
Die selbe Herangehensweise wird auch angewandt wenn die Formel sich nicht zwischen Allaussage und Existenzquantor abwechselt. Dann darf der jeweilige Spieler einfach entsprechend mehreren Variablen gleichzeitig einem Wert zuweisen.
Also ist $\phi\in\mathrm{TQBF}$ gdw. $\phi\in\mathrm{FORMULA\text{-}GAME}$. Aus dem Satz TQBF ist PSPACE-vollständig folgt, das FORMULA-GAME PSPACE-vollständig ist.