Erfüllbarkeitsproblem für quantifizierte boolesche Formeln

Einfache Sprache

Erfüllbarkeitsproblem für quantifizierte boolesche Formeln

Das Entscheidungsproblem TQBF stellt die Frage ob Prädikatenlogische Formeln (also mit Quantoren (Quantor))erfüllbar sind.

Als Sprache formuliert:

$$ \textrm{TQBF} = \left\{\langle\phi\rangle\mid \phi\text{ ist eine erfüllbare voll quantifizierte prädikatenlogische Formel}\right\}$$

• Satz TQBF ist PSPACE-vollständig