What Does the Answer to a SAT Problem Look Like, is it YES or NO or is it an arrangement of Satisfying Values?

92 Views Asked by At

I am having difficulty understanding what a SAT problem is asking. The answer given by com here says the answer to a SAT problem is YES or NO and we don't care about the satisfying values for the literals. If this is the case can someone link me to either the definitions (preferably for 3 SAT) stating this or work showing why this is the most useful way to think about these problems?

1

There are 1 best solutions below

2
On

The answer is TRUE / FALSE according to wikipedia: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

But you can easily use an algorithm that provides a yes/no answer to find a satisfying solution, if one exists. Simply fix one of the variables to be TRUE and use your algorithm to see if there is still a satisfying solution. If not, it means that variable must be FALSE. You can then repeat with the next variable until all your variables are fixed, which takes $O(n)$ calls to your algorithm.