Problem opisany w zadaniu jest NP trudny. Dlaczego? Otóż pytanie, czy formuła \phi \in QBF, w której występują tylko kwantyfikatory \exists , jest prawdziwa, to właściwie pytanie, czy formuła \phi' pozbawiona kwantyfikatorów jest spełnialna. Gdy dokładamy kwantyfikatory \forall, sytuacja zmienia się. Jednak, ponieważ mamy tylko dwa takie kwantyfikatory \forall p \forall q, to możemy rozpatrzyć 4 przypadki - za każdym razem podstawiając pod p i q różne wartości sprawdzić, czy wtedy formuła \phi' jest spełnialna. A to możemy, gdy dysponujemy niedeterministyczną maszyną Turinga, zrobić w czasie wielomianowym (po prostu cztery razy „zgadując” wartościowanie i sprawdzając, czy zawsze jest prawdziwe).