1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ What is your question? $\endgroup$
    – Nathaniel
    Mar 21, 2022 at 19:25
  • $\begingroup$ How I'm meant to show that the problem is in $NP^{NP}$ $\endgroup$ Mar 22, 2022 at 4:44
  • $\begingroup$ As you already have a sketch of a proof, you should be more specific! $\endgroup$
    – Nathaniel
    Mar 22, 2022 at 7:27
  • $\begingroup$ 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) $\endgroup$ Mar 22, 2022 at 7:43

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.