Here's the question:

Assume there exists a polynomial time machine $M$ that receives two formulas $\varphi_1,\varphi_2$ and satisfies the following:

  • If $\varphi_1 \in \mathrm{SAT}$ and $\varphi_2 \notin \mathrm{SAT}$, then $M(\varphi_1,\varphi_2)=1$
  • If $\varphi_1 \notin \mathrm{SAT}$ and $\varphi_2 \in \mathrm{SAT}$, then $M(\varphi_1,\varphi_2)=0$

Show that there also exists a polynomial time algorithm for SAT.

Note that we have no guarantee for the output of $M(\varphi_1,\varphi_2)$ whenever $\varphi_1,\varphi_2$ are both satisfiable (or when both are not).

Can I get any hint on how to start the solution?

  • $\begingroup$ hint: Can you make a formula that is UNSAT iff the input formula is SAT? $\endgroup$
    – Jake
    Commented May 12, 2020 at 22:12
  • 1
    $\begingroup$ I tried to do that before posting the question but that didn't work for me. It seems hard to make a formula that is UNSAT. I posted a question of that before here and somebody said that I can't do it in P. $\endgroup$ Commented May 12, 2020 at 22:18
  • 1
    $\begingroup$ cs.stackexchange.com/questions/125615/… $\endgroup$ Commented May 12, 2020 at 22:19
  • $\begingroup$ What does SAT contain exactly? Is it restricted to CNF formulas? $\endgroup$
    – Steven
    Commented May 12, 2020 at 22:20
  • 1
    $\begingroup$ Not exactly, it contains all the formulas that are consisted of "and" "or" "not" "->" "<->" gates and variables AND the formula = T for some values "T\F" for the variables $\endgroup$ Commented May 12, 2020 at 22:24

1 Answer 1


Here is something your oracle can do: if you are given two formulas $\alpha,\beta$, and are guaranteed that at least one of them is satisfiable, then you can find one of them which is satisfiable by calling $M(\alpha,\beta)$: if $M(\alpha,\beta) = 1$ then $\alpha$ is satisfiable, and if $M(\alpha,\beta) = 0$ then $\beta$ is satisfiable.

Given a satisfiable formula $\varphi$ over $x_1,\ldots,x_n$, you can use this to find a satisfying assignment, variable by variable: at each step, you consider assigning the variable the two possible truth values, and use the method described above to find an assignment under which the formula is still satisfiable. Finally, you can check whether the supposed satisfying assignment indeed satisfies $\varphi$. If so, $\varphi$ is satisfiable. Otherwise, it isn't.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.