2
$\begingroup$

I'm interested in 3SAT and querying an oracle. Suppose we had an oracle that can decide, on an input boolean formula $\phi$, whether there exists any assignment to the variables that makes the formula true. Note: this does not say what the assignment to the variables is, just that there exists one.

My main question is: can we get the actual solution of the formula in polynomial time, using the oracle?

My first thought was that no, it is impossible because the oracle cannot help you with an assignment (i.e., if I gave an assignment to the variables, the oracle's answer does not change). However, just because this technique does not work does not mean that no techniques will.

I then thought to give an assignment to the first variable $x_1$, and then use that to work on the next variables; however, I don't know how to progress from there without trying all possible combinations (i.e., running in time $O(2^n)$).

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
4
$\begingroup$

You have the right idea. Suppose you have a SAT oracle and an instance $I$ of 3SAT (or whatever SAT-ish class you like) containing $n$ variables, $x_1, x_2, \dotsc x_n$. You could then do this:

send I to the oracle
if the oracle answers "not satisfiable"
   quit
else
   j = 1
   I_0 = I
   repeat
      transform I_{j-1} to I_j by substituting x_j = 1
      send I_j to the oracle
      if the answer is "satisfiable"
         save x_j = 1
      else 
         save x_j = 0
         transform I_{j-1} to I_j by substituting x_j = 0
      j = j + 1
  until j = n

When the algorithm terminates, you'll have saved a satisfying collection of values for all the variables. This will be linear in $n$ (times the steps necessary to do the substitutions, which will be polynomial in the length of $I$).

Improve this answer
$\endgroup$
5
  • $\begingroup$ I've gone through your algorithm which makes good sense but have a question on the running time. You're saying that "it will be linear in n times the steps necessary to do the substitutions, which will be polynomial in the length of I". So what will the worst case running time be in this case? $\endgroup$
    – Force444
    Sep 14, 2015 at 21:10
  • $\begingroup$ Worst case is you repeat n times and substitution is performed twice per iteration. Right? $\endgroup$
    – Force444
    Sep 14, 2015 at 21:12
  • $\begingroup$ @D.Singh. Yup. Looks that way to me. $\endgroup$
    – Rick Decker
    Sep 14, 2015 at 21:17
  • $\begingroup$ So is it O(n^2) ? $\endgroup$
    – Force444
    Sep 14, 2015 at 21:21
  • $\begingroup$ @D.Singh. Not in general. The key here is the two "transform" steps. They will go through the clauses and substitute a value for a particular variable. That could take time proportional to the length of the clauses. $\endgroup$
    – Rick Decker
    Sep 14, 2015 at 23:38

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