Let F be a uniformly distributed random k-SAT formula with n variables and m clauses. We present a polynomial time algorithm that finds a satisfying assignment of F with high probability for constraint densities m/n<2^k ln(k)/k.
Previously no efficient algorithm was known to find solutions with a non-vanishing probability beyond m/n=1.817 2^k/k [Frieze and Suen, Journal of Algorithms 1996]. The density 2^k ln(k)/k matches the replica symmetry breaking transition, whose existence was recently established rigorously [Achlioptas and Coja-Oghlan, FOCS 2008].
Copyright. All Rights Reserved.