The second paragraph of RJK's response deserves more detail.
Let $\phi$ be a formula in conjunctive normal form, with m clauses, n variables, and at most k variables per clause. Suppose we want to determine if $\phi$ has a satisfying assignment. Formula $\phi$ is an instance of the k-SAT decision problem.
When there are few clauses (so m is quite small compared to n), then it is almost always possible to find a solution. A simple algorithm will find a solution in roughly linear time in the size of the formula.
When there are many clauses (so m is quite large compared to n), then it is almost always the case that there is no solution. This can be shown by a counting argument. However, during search it is almost always possible to prune large parts of the search space by means of consistency techniques, because the many clauses interact so extensively. Establishing unsatisfiability can then usually be done efficiently.
In 1986 Fu and Anderson conjectured a relationship between optimisation problems and statistical physics, based on spin glass systems. Although they used sentences like
Intuitively, the system must be sufficiently large, but it is difficult to be more specific.
they do actually give specific predictions.
- Y Fu and P W Anderson. Application of statistical mechanics to NP-complete problems in combinatorial optimisation, J. Phys. A. 19 1605, 1986. doi: 10.1088/0305-4470/19/9/033
Based on arguments from statistical physics, Zecchina and collaborators conjectured that k-SAT should become hard when $\alpha = m/n$ is near a critical value. The precise critical value depends on k, but is in the region of 3.5 to 4.5 for 3-SAT.
- Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky. Determining computational complexity from characteristic `phase transitions', Nature 400 133–137, 1999. (doi: 10.1038/22055 , free version)
Friedgut provided a rigorous proof of these heuristic arguments. For every fixed value of k, there are two thresholds $\alpha_1 < \alpha_2$. For $\alpha$ below $\alpha_1$, there is a satisfying assignment with high probability. For a value of $\alpha$ above $\alpha_2$, formula $\phi$ is unsatisfiable with high probability.
- Ehud Friedgut (with an appendix by Jean Bourgain), Sharp thresholds of graph properties, and the $k$-sat problem, J. Amer. Math. Soc. 12 1017–1054, 1999. (PDF)
Dimitris Achlioptas worked on many of the remaining issues, and showed that the above argument holds for constraint satisfaction problems, too. These are allowed to use more than just two values for each variable. One key paper shows rigorously why the Survey Propagation algorithm works so well to solve random k-SAT instances.
- A. Braunstein, M. Mézard, R. Zecchina, Survey propagation: An algorithm for satisfiability, Random Structures & Algorithms 27 201–226, 2005. doi: 10.1002/rsa.20057
- D. Achlioptas and F. Ricci-Tersenghi, On the Solution-Space Geometry of Random Constraint Satisfaction Problems,
STOC 2006, 130–139. (preprint)