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$:
- $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.
- $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.