1
$\begingroup$

We're given a 3-SAT problem described by 3-CNF formula where each clause consists of 3 boolean variables.

A greedy algorithm is suggested to solve this problem: the algorithm goes through each variable and calculates two values for each variable $u_i$:

  1. $X$ - the number of clauses which are not yet TRUE but which would be become TRUE if we were to assign TRUE to the variable.
  2. $Y$ - the number of clauses which are not yet TRUE but which would become TRUE if we were to assign FALSE to the variable.

If $X>Y$ then we assign TRUE to the variable else we assign FALSE. If $X=Y$ then the algorithm will randomly determine whether to assign TRUE or FALSE to the variable.

I need to come up with a counter example to the algorithm which will show that the algorithm fails even though the formula itself is satisfiable.

I thought of the following example: $$ (u_1 \lor u_2 \lor u_3)\land(\lnot u_1 \lor \lnot u_2 \lor \lnot u_3)\land (u_1 \lor u_2 \lor u_3) $$

The algorithm would assign TRUE to all the variables $u_1,u_2,u_3$ because separately if $u_i$ is TRUE then 2 clauses can be satisfied. But this formula on the whole will not be satisfied with such an assignment. However if we were to assign $u_1=TRUE, u_2=TRUE, u_3=FALSE$ then the formula would be satisfied.

The example seems to simple to me I'm wondering if I missed something.

$\endgroup$
1
$\begingroup$

No that won't work.

The greedy algorithm described in your quote would start by setting $u_1$ to true, because that satisfies two clauses, whereas setting $u_1$ to false would satisfy only one clause.

Then it looks at $u_2$. Setting $u_2$ to true would satisfy $0$ clauses that are not already satisfied given our decision for $u_1$. But setting $u_2$ to false would satisfy $1$ new clause. So $u_2$ gets set to false.

Now all three clauses are satisfied, so $u_3$ gets set randomly.


In comments Yos suggested a counterexample that will actually work, though one that repeats identical clauses more than one time. One may argue whether the definition of 3SAT ought to contain a speficiation that each clause appears at most one.

Here is a more involved counterexample that doesn't repeat any clause, and has the additional nice feature that no matter which order the greedy algorithm considers the variables in, it will fail to satisfy the formula (even though that can obviously be done by setting every variable to false): $$ \phantom{\land{}} (\neg a\lor b\lor c)\land(\neg b\lor a\lor c)\land(\neg c\lor a\lor b)\land(\neg d\lor a\lor b)\land(\neg e\lor a\lor b)\\ \land(\neg a\lor b\lor d)\land(\neg b\lor a\lor d)\land(\neg c\lor a\lor d)\land(\neg d\lor a\lor c)\land(\neg e\lor a\lor c)\\ \land(\neg a\lor b\lor e)\land(\neg b\lor a\lor e)\land(\neg c\lor a\lor e)\land(\neg d\lor a\lor e)\land(\neg e\lor a\lor d)\\ \land(\neg a\lor c\lor d)\land(\neg b\lor c\lor d)\land(\neg c\lor b\lor d)\land(\neg d\lor b\lor c)\land(\neg e\lor b\lor c)\\ \land(\neg a\lor c\lor e)\land(\neg b\lor c\lor e)\land(\neg c\lor b\lor e)\land(\neg d\lor b\lor e)\land(\neg e\lor b\lor d)\\ \land(\neg a\lor d\lor e)\land(\neg b\lor d\lor e)\land(\neg c\lor d\lor e)\land(\neg d\lor c\lor e)\land(\neg e\lor c\lor d)\\ \land(\neg a\lor \neg b\lor \neg c)\land(\neg a\lor \neg b\lor \neg d)\land(\neg c\lor \neg d\lor \neg e) $$

The first $30$ clauses are simply every possible clause with variables drawn from $a,b,c,d,e$ that has one negative and two positive atoms. Between them, they contain enough positive appearances that the first four variables considered by the greedy algorithm will be set to true by the greedy algorithm, no matter which ones they are -- and when that happens, one of the $3$ final clauses will be impossible to satisfy.

$\endgroup$
8
  • $\begingroup$ Can a literal appear multiple times in a clause? For example $(x_2\lor x_2\lor x_2)$ $\endgroup$ – Yos Nov 19 '17 at 17:29
  • $\begingroup$ @Yos : Depends on how exactly you have defined 3SAT. Check your textbook. $\endgroup$ – hmakholm left over Monica Nov 19 '17 at 17:53
  • $\begingroup$ I thought there were some universal conventions, the book doesn't say anything about it but I assume this is not allowed because the solution would be too easy then. What should be the right direction? How do graphs come into play in this problem? $\endgroup$ – Yos Nov 19 '17 at 17:56
  • $\begingroup$ @Yos: it makes no real difference for NP-completeness, which is the principal reason to be interested in 3SAT specifically, so many authors don't bother to specify it exactly. $\endgroup$ – hmakholm left over Monica Nov 19 '17 at 18:01
  • 1
    $\begingroup$ @Yos, yes dag sounds like a valid example. $\endgroup$ – hmakholm left over Monica Nov 19 '17 at 18:42

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.