Random k-SAT is the single most intensely studied example of a random constraint satisfaction problem. But despite substantial progress over the past decade, the threshold for the existence of satisfying assignments is not known precisely for any k≥3. The best current results, based on the second moment method, yield upper and lower bounds that differ by an additive k ⋅ ln2 2, a term that is unbounded in k (Achlioptas, Peres: STOC 2003). The basic reason for this gap is the inherent asymmetry of the Boolean values 'true' and 'false' in contrast to the perfect symmetry, e.g., among the various colors in a graph coloring problem. Here we develop a new asymmetric second moment method that allows us to tackle this issue head on for the first time in the theory of random CSPs. This technique enables us to compute the k-SAT threshold up to an additive ln2-1 2+O(1 k) 0.19. Independently of the rigorous work, physicists have developed a sophisticated but non-rigorous technique called the "cavity method" for the study of random CSPs (Mezard, Parisi, Zecchina: Science 2002). Our result matches the best bound that can be obtained from the so-called "replica symmetric" version of the cavity method, and indeed our proof directly harnesses parts of the physics calculations.
Let @math be a uniformly distributed random @math -SAT formula with @math variables and @math clauses. We present a polynomial time algorithm that finds a satisfying assignment of @math with high probability for constraint densities @math , where @math . Previously no efficient algorithm was known to find satisfying assignments with a nonvanishing probability beyond @math [A. Frieze and S. Suen, J. Algorithms, 20 (1996), pp. 312-355]. The Lovasz Local Lemma discovered by Erdős and Lovasz in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, Jozsef Beck was the first to demonstrate that a constructive variant can be given under certain more restrictive conditions, starting a whole line of research aimed at improving his algorithm's performance and relaxing its restrictions. In the present article, we improve upon recent findings so as to provide a method for making almost all known applications of the general Local Lemma algorithmic. We consider the performance of two algorithms, GUC and SC studied by M. T. Chao and J. Franco SIAM J. Comput.15(1986), 1106?1118;Inform. Sci.51(1990), 289?314 and V. Chvatal and B. Reed in“Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, 1992,” pp. 620?627, when applied to a random instance ? of a boolean formula in conjunctive normal form withnvariables and ?cn? clauses of sizekeach. For the case wherek=3, we obtain the exact limiting probability that GUC succeeds. We also consider the situation when GUC is allowed to have limited backtracking, and we improve an existing threshold forcbelow which almost all ? is satisfiable. Fork?4, we obtain a similar result regarding SC with limited backtracking.