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)$).

$\endgroup$

marked as duplicate by Kyle Jones, Community Mar 31 '15 at 22:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\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$).

$\endgroup$
  • $\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$ – DSF Sep 14 '15 at 21:10
  • $\begingroup$ Worst case is you repeat n times and substitution is performed twice per iteration. Right? $\endgroup$ – DSF Sep 14 '15 at 21:12
  • $\begingroup$ @D.Singh. Yup. Looks that way to me. $\endgroup$ – Rick Decker Sep 14 '15 at 21:17
  • $\begingroup$ So is it O(n^2) ? $\endgroup$ – DSF Sep 14 '15 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 '15 at 23:38

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