====== JFiZO - Zadanie 09.135 ======
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).