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

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?