Determining computational complexity from characteristic ‘phase transitions’
Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick et al. · Nature · 1999
Cited by 790 works. doi:10.1038/22055
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- The complexity of theorem-proving procedures
- A Computing Procedure for Quantification Theory
- Spin Glass Theory and Beyond
- Spin Glass Theory and Beyond
- Formation of Glasses from Liquids and Biopolymers
- The simplest spin glass
- A linear-time algorithm for testing the truth of certain quantified boolean formulas
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Sharp thresholds of graph properties, and the $k$-sat problem