# Showing that a QBF in 3DNF form is in $NP^{NP}$

Consider the problem of checking whether a quantified Boolean formula of the form $$∃X_1 . . . ∃X_n ∀Y_1 . . . ∀Y_m \phi$$, for $$\phi$$ in $$3DNF$$ over $$X_1, . . . , X_n, Y_1, . . . , Y_m$$, is true.

I'm trying to show that it's in $$NP^{NP}$$

My attempt (probably not correct, it's a guess):

Consider the following problem: $$∀Y_1 . . . ∀Y_m \phi$$ where $$\phi$$ is in $$3DNF$$. This is equivalent to solving a DNF Tautology problem, where $$\phi \in DNF-TAUT \iff (not)\phi \in CNF-UNSAT$$ (the problem of given a CNF formula finding out if there's no satisfying assignments).

$$CNF-UNSAT \in co-NP$$ and co-NP problems can be simulated using NP oracles, so we can use an NP oracle to solve that part of the problem.

Then the $$\exists$$ parts is equivalent to finding a satisfiable formula. Since $$SAT \in NP$$, together, they can be simulated on an $$NP^{NP}$$ oracle.

• What is your question? Mar 21, 2022 at 19:25
• How I'm meant to show that the problem is in $NP^{NP}$ Mar 22, 2022 at 4:44
• As you already have a sketch of a proof, you should be more specific! Mar 22, 2022 at 7:27
• I'm not entirely sure if my proof is correct given that I'm not sure when we'd make the oracle calls to solve the $\forall$ parts while solving an instance of SAT (Given that they're both together, and the $\exists$ parts and the $\forall$ parts aren't independent) Mar 22, 2022 at 7:43