ANALYSIS OF 2 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 f ormula in conjunctive normal form with n variables and right perpendic ular 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 backtr acking, 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 Acad emic Press, Inc.