up E. Koutsoupias and C. H. Papadimitriou. On the greedy algorithm for satisfiability. Information Processing Letters, 43(1):53--55, August 1992.

Abstract:

We show that for the vast majority of satisfiable 3CNF formulae, the local search heuristic that starts at a random truth assignment, and repeatedly flips the variable that improves the number of satisfied clauses the most, almost always succeeds in discovering a satisfying truth assignment.

 Postscript    Pdf    BibTeX  
 


Elias Koutsoupias / elias_at_di.uoa.gr