# GSAT incompleteness example

The GSAT (Greedy Satisfiability) algorithm can be used to find a solution to a search problem encoded in CNF. I'm aware that since GSAT is greedy, it is incomplete (which means there would be cases where a solution might exist, but GSAT cannot find it). From the following link, I learned that this can happen when flipping variables greedily traps us in a cycle such as I → I' → I'' → I.

http://www.dis.uniroma1.it/~liberato/ar/incomplete/incomplete.html

I've been trying quite hard to come up with an actual instance that can show this, but have not been able to (and could not find examples elsewhere). Any help would be much appreciated. Thanks :)

P.S. I'm not talking about "hard" k-SAT problems in which the ratio of variables to clauses approaches 4.3. I'm just looking for a simple example, possibly involving the least number of variables and/or clauses required.

• GSAT is actually a local search algorithm. – Yuval Filmus Feb 27 '14 at 5:45

The original paper contains such an example (on page 5): $$\begin{gather*} (1 \lor \lnot 2 \lor 3) \land (1 \lor \lnot 3 \lor 4) \land (1 \lor \lnot 4 \lor \lnot 2) \land (1 \lor 5 \lor 2) \land (1 \lor \lnot 5 \lor 2) \land \\ (\lnot 1 \lor \lnot 6 \lor 7) \land (\lnot 1 \lor \lnot 7 \lor 6) \land \dots \land (\lnot 1 \lor \lnot 98 \lor 99) \land (\lnot 1 \lor \lnot 99 \lor 6) \end{gather*}$$ The first five clauses force $1$ to hold. Indeed, suppose that $\lnot 1$. Clauses 4 and 5 force $2$, and so clauses 1 and 3 force $3 \land \lnot 4$, contradicting 2. The entire formula is satisfiable, for example by the all-true assignment.
If the starting assignment is not satisfiable or very close to satisfiable, then the authors claim that the large number of clauses of the form $(\lnot 1 \lor \cdot \lor \cdot)$ will ensure that $1$ remains false throughout the algorithm. See if you can substantiate this claim.