The Statistical Mechanics of K-Satisfaction

Scott Kirkpatrick, Géza Györgyi, Naftali Tishby, Lidror Troyansky

NeurIPS 1993 pp. 439-446

/neurips/1993/kirkpatrick1993neurips-statistical/

Abstract

The satisfiability of random CNF formulae with precisely k vari(cid:173) ables per clause ("k-SAT") is a popular testbed for the performance of search algorithms. Formulae have M clauses from N variables, randomly negated, keeping the ratio a = M / N fixed . For k = 2, this model has been proven to have a sharp threshold at a = 1 between formulae which are almost aways satisfiable and formulae which are almost never satisfiable as N --jo 00 . Computer experi(cid:173) ments for k = 2, 3, 4, 5 and 6, (carried out in collaboration with B. Selman of ATT Bell Labs). show similar threshold behavior for each value of k. Finite-size scaling, a theory of the critical point phenomena used in statistical physics, is shown to characterize the size dependence near the threshold. Annealed and replica-based mean field theories give a good account of the results.

PDF NeurIPS Semantic Scholar

Cite

Text

Kirkpatrick et al. "The Statistical Mechanics of K-Satisfaction." Neural Information Processing Systems, 1993.

Markdown

[Kirkpatrick et al. "The Statistical Mechanics of K-Satisfaction." Neural Information Processing Systems, 1993.](https://mlanthology.org/neurips/1993/kirkpatrick1993neurips-statistical/)

BibTeX

@inproceedings{kirkpatrick1993neurips-statistical,
  title     = {{The Statistical Mechanics of K-Satisfaction}},
  author    = {Kirkpatrick, Scott and Györgyi, Géza and Tishby, Naftali and Troyansky, Lidror},
  booktitle = {Neural Information Processing Systems},
  year      = {1993},
  pages     = {439-446},
  url       = {https://mlanthology.org/neurips/1993/kirkpatrick1993neurips-statistical/}
}