I\'m interested in 3SAT and querying an oracle. Suppose we had an oracle that ca

Question

I'm interested in 3SAT and querying an oracle. Suppose we had an oracle that can decide, on an input boolean formula ?, 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 x1, 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(2n)).

Explanation / Answer

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, x1,x2,

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.