Rémi Monasson, Riccardo Zecchina, et al.
Random Structures and Algorithms
Determining the satisfiability of randomly generated Boolean expressions with k variables per clause is a popular test for the performance of search algorithms in artificial intelligence and computer science. It is known that for k = 2, formulas are almost always satisfiable when the ratio of clauses to variables is less than 1; for ratios larger than 1, the formulas are almost never satisfiable. Similar sharp threshold behavior is observed for higher values of k. Finite-size scaling, a method from statistical physics, can be used to characterize size-dependent effects near the threshold. A relationship can be drawn between thresholds and computational complexity.
Rémi Monasson, Riccardo Zecchina, et al.
Random Structures and Algorithms
Scott Kirkpatrick
Journal of Statistical Physics
Rémi Monasson, Riccardo Zecchina, et al.
Random Structures and Algorithms
Scott Kirkpatrick, Thomas P. Eggarter
Physical Review B