1
$\begingroup$

The 3-co-SAT problem consists of deciding whether if a 3CNF formula, has an unsatisfiable assignment of variables, i.e., assignment of variables that evaluates to 0.

We know that 3-co-SAT is in coNP, however, I do not understand why it is also not in P? It seems to be very easy to check whether if there exists an unsatisfiable assignment of variables as follows:

  1. Iteratively go through each clause.

  2. For each clause try $2^3 = 8$ possible variable assignments. If there exists an assignment that makes the clause evaluate to False, accept.

  3. If no clauses evaluated to False, reject.

This algorithm has runtime $8m$ where $m$ is the number of clauses, and it accepts a string if it is in coSAT no?

$\endgroup$
1
  • 5
    $\begingroup$ The definition of 3-co-SAT is deciding whether a formula is unsatisfiable, no? Not only whether it has some unsatisfying assignment. $\endgroup$
    – kviiri
    Commented Feb 23, 2023 at 6:22

1 Answer 1

4
$\begingroup$

co-SAT is not asking whether there exists an unsatisfying assignment, it is asking if every assignment evaluates to false.

$\endgroup$

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.