On belief propagation guided decimation for random k-SAT

Amin Coja-Oghlan

Let F be a uniformly distributed random k-SAT formula with n variables and m clauses. Non-constructive arguments show that F is satisfiable for clause/variable ratios m/n< r(k)~2^k…