2
$\begingroup$

Does a 3-SAT problem, where in each clause there is at least a negative-literal, always has a solution?

After looking at it, seems to me that the answer is yes, but maybe there is something I am not seeing.

$\endgroup$

1 Answer 1

1
$\begingroup$

Consider the all-zeroes assignment, $x_1=x_2=\cdots=x_n=0$.

What if all clauses have a positive literal?

$\endgroup$
1
  • $\begingroup$ Doesn't seem to be enough information to determine if there is a solution, if all literals where positive I would say that there isn't any solution. $\endgroup$
    – wallek876
    May 21, 2019 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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