building a polynomial algorithm that solves SAT when given a polynomial TM that solves SAT on two formulas

Question

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?

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.