Lower bounds for random 3-SAT via differential equations (Q5958806): Difference between revisions

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.