Random Satisfiability
Achlioptas Dimitris · Frontiers in artificial intelligence and applications · 2009
In the last twenty years a significant amount of effort has been devoted to the study of randomly generated satisfiability instances. While a number of generative models have been proposed, uniformly random k-CNF formulas are by now the dominant and most studied model. One reason for this is that such formulas enjoy a number of intriguing mathematical properties, including the following: for each k≥3, there is a critical value, rk, of the clauses-to-variables ratio, r, such that for r rkit is unsatisfiable with probability that tends to 1 as n→∞.