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

We consider the performance of two algorithms, GUC and SC studied by M. T. Chao and J. France [SLAM 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 omega of a boolean formula in conjunctive normal form with n variables and right perpendicular cn left perpendicular 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 greater than or equal to 4, we obtain a similar result regarding SC with limited backtracking. (C) 1996 Academic Press, Inc.