QBF steht für quantified Boolean formula: eine aussagenlogische Formel mit Quantoren über Boolesche Variablen.
Das Wahrheitsproblem für vollständig quantifizierte Boolesche Formeln ist PSPACE-vollständig.