10
$\begingroup$

Is the problem of determining whether or not a given Boolean expression is satisfiable computationally distinct from actually finding a solution to the expression?

In other words, is there another way of finding that a given expression is satisfiable without explicitly determining the 'right settings' for the Boolean variables? Or do all possible proofs reduce in polynomial time to the 'right settings'?

Forgive my ignorance, I am only an engineering student. Wikipedia seems to imply that the act of just finding SAT or UNSAT is NP-complete.

$\endgroup$

migrated from cstheory.stackexchange.com Aug 29 '14 at 1:05

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 8
    $\begingroup$ Short answer: the problem of finding a satisfying assignment is computationally as hard as deciding if one exists. The idea is that given an algorithm which decides satisfiability it can be used to efficiently construct a satisfying assignment. Check out en.wikipedia.org/wiki/… $\endgroup$ – John D. Aug 28 '14 at 20:46
  • 2
    $\begingroup$ I thought UNSAT was coNP-complete? $\endgroup$ – G. Bach Aug 29 '14 at 14:09
14
$\begingroup$

As mentioned in a comment, any method of determining satisfiability of a Boolean formula can be easily converted into a method for finding the satisfying variable assignment. This is because all NP-complete problems are downward self-reducible.

From Wikipedia:

Self-reducibility

The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment. First, the question is asked on the given formula $Φ$. If the answer is "no", the formula is unsatisfiable. Otherwise, the question is asked on the partly instantiated formula $Φ$$\{x_1=TRUE\}$, i.e. $Φ$ with the first variable $x_1$ replaced by $TRUE$, and simplified accordingly. If the answer is "yes", then $x_1=TRUE$, otherwise $x_1=FALSE$. Values of other variables can be found subsequently in the same way. In total, $n+1$ runs of the algorithm are required, where $n$ is the number of distinct variables in $Φ$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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