Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

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/n grow, it is rather easy to see that for d ≥ ε^-k ln 2, F becomes whp unsatisfiable after smoothing.

We show that a lower density that behaves roughly like ε^-k+1 suffices for this purpose. We also show that our bound on d is nearly best possible in the sense that there are k-CNF formulas F of slightly lower density that whp remain satisfiable after smoothing.

One consequence of our proof is a new lower bound of Ω(2^k/k²) on the density up to which Walksat solves random k-CNFs in polynomial time whp. We are not aware of any previous rigorous analysis showing that Walksat is successful at densities that are increasing as a function of k.

REFERENCES

• 1: D. Achlioptas and A. Coja-Oghlan. Algorithmic barriers from phase transitions. preprint, 2008.
• 2: D. Achlioptas and Y. Peres. The threshold for random k-SAT is 2^k log 2 -- O(k). Journal of the AMS, 17(4):947--973, 2004.
• 3: Mikhail Alekhnovich , Eli Ben-Sasson, Linear Upper Bounds for Random Walk on Small Density Random $3$-CNFs, SIAM Journal on Computing, v.36 n.5, p.1248-1263, December 2006 [doi>10.1137/S0097539704440107]
• 4: Andrei Z. Broder , Alan M. Frieze , Eli Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.322-330, January 25-27, 1993, Austin, Texas, United States
• 5: Ming-Te Chao , John Franco, Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem, Information Sciences: an International Journal, v.51 n.3, p.289-314, Aug. 1990 [doi>10.1016/0020-0255(90)90030-E]
• 6: V. Chvatal , B. Reed, Mick gets some (the odds are on his side) (satisfiability), Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, p.620-627, October 24-27, 1992 [doi>10.1109/SFCS.1992.267789]
• 7: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 8: Uriel Feige, Refuting Smoothed 3CNF Formulas, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.407-417, October 21-23, 2007 [doi>10.1109/FOCS.2007.59]
• 9: U. Feige and E. Ofek. Easily refutable subformulas of large random 3cnf formulas. Theory of Computing, 3(1):25--43, 2007.
• 10: Abraham Flaxman, A spectral technique for random satisfiable 3CNF formulas, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: E. Friedgut. Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc., 12(4):1017--1054, 1999.
• 12: Alan Frieze , Stephen Suen, Analysis of two simple heuristics on a random instance of k-SAT, Journal of Algorithms, v.20 n.2, p.312-355, March 1996 [doi>10.1006/jagm.1996.0016]
• 13: D. Kleitman. On a combinatorial conjecture of Erdős. J. Combinatorial Theory, pages 209--214, 1966.
• 14: Michael Krivelevich , Benny Sudakov , Prasad Tetali, On smoothed analysis in dense graphs and formulas, Random Structures & Algorithms, v.29 n.2, p.180-193, September 2006 [doi>10.1002/rsa.v29:2]
• 15: Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
• 16: Christos H. Papadimitriou, On selecting a satisfying truth assignment (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.163-169, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185365]
• 17: Andrew J. Parkes, Scaling Properties of Pure Random Walk on Random 3-SAT, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.708-713, September 09-13, 2002
• 18: Daniel A. Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), v.51 n.3, p.385-463, May 2004 [doi>10.1145/990308.990310]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms