Analysis of two simple heuristics on a random instance of k-SAT

Abstract: "We consider the performance of two algorithms, GUC and SC studied by Chao and Franco [2], [3], and Chvátal and Reed [4], when applied to a random instance [omega] of a boolean formula in conjunctive normal form with n variables and [cn] clauses of size k each. For the case where k = 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 for c below which almost all [omega] is satisfiable. For k [> or =] 4, we obtain a similar result regarding SC with limited backtracking."