On smoothed k-CNF formulas and the Walksat algorithm

摘要

In this paper we study the model of ε-smoothed k-CNF formulas. Starting from an arbitrary instance F with n variables and m = dn clauses, apply the ε-smoothing operation of flipping the polarity of every literal in every clause independently at random with probability ε. Keeping ε and k fixed, and letting the density d = m grow, it is rather easy to see that for d ≥ ε-k ln 2, F becomes whp unsatisfiable after smoothing.