Solving random satisfiable 3CNF formulas in expected polynomial time
Michael Krivelevich, Dan Vilenchik · 2006
1 Introduction and Results 1.1 The Planted 3SAT Distribution A 3CNF for-mula over the variables x1, x2,..., xn is a conjunction ofclauses C1, C2,..., Cm where each clause is a disjunctionof three literals. Each literal is either a variable or its