1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ hint: Can you make a formula that is UNSAT iff the input formula is SAT? $\endgroup$ 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$ 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

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.