Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
GSAT is actually a local search algorithm. –  Yuval Filmus Feb 27 at 5:45
add comment

1 Answer

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.

share|improve this answer
    
Yuval, thanks for your answer. I will certainly look into it. Do you think there is a smaller set of clauses that could illustrate the same? I'm only looking for a set of clauses and some random initial assignment that throws GSAT off (potentially throws it into a loop so that it has to restart). Thanks again! :) –  sarora Feb 27 at 7:09
    
Certainly the number 99 here is not sacred, and a much smaller number would do. I suspect that there are even simpler examples; keep looking for them! –  Yuval Filmus Feb 27 at 12:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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