It is widely believed that the probability of satisfiability for random k-SAT formulae exhibits a sharp threshold as a function of their clauses-to-variables ratio. For the most studied case, k = 3, there have been a number of results during the last decade providing upper and lower bounds for the threshold's potential location. All lower bounds in this vein have been algorithmic, i.e., in each case a particular algorithm was shown to satisfy random instances of 3-SAT with probability 1 - o(1) if the clauses-to-variables ratio is below a certain value. We show how differential equations can serve as a generic tool for analyzing such algorithms by rederiving most of the known lower bounds for random 3-SAT in a simple, uniform manner. (C) 2001 Elsevier Science B.V. All rights reserved. [References: 31]
展开▼
