1
$\begingroup$

I am currently trying to solve the following problem but I am unsure how to go about it. The problem states:

Suppose that someone gives you a polynomial-time algorithm to decide 3-SAT. Describe how to use this algorithm to find a satisfying assignment in polynomial time.

To my understanding the 3-SAT is simply a conjunction of any 3 disjunctions that turns out to be true (i.e. something like (x1 | x2 | x3) & (x4 | x5| x6) where | represent or and & represents and). In this case you could have used any ordering of the variables and you could have negated them at your pleasure. Furthermore You can keep adding conjunctions, but each one has to have 3 variables. Please correct me if I am wrong in any statement above.

Now, they want us to find a satisfying assignment in polynomial time, meaning values of x1, x2, x3, x4, x5, x6 that make the value true. However, isn't that what we are given in the first place? I am confused as to what to do and if I am interpreting the question correctly.

$\endgroup$
1

1 Answer 1

6
$\begingroup$

The algorithm that decides 3-SAT just answers yes or no, satisfiable or not. It doesn't (directly) give you an assignment for the variables. You have to use the decision algorithm as a black box to find an assignment of the variables. You should try adding a something to your formula that lets you deduce the assignment of a particular variable without changing the satisfiability.

$\endgroup$

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