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
    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$ May 12, 2020 at 22:18
  • 1
    $\begingroup$ cs.stackexchange.com/questions/125615/… $\endgroup$ May 12, 2020 at 22:19
  • $\begingroup$ What does SAT contain exactly? Is it restricted to CNF formulas? $\endgroup$
    – Steven
    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$ 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, privacy policy and cookie policy

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