Determining computational complexity from characteristic ‘phase transitions’
- 8 July 1999
- journal article
- research article
- Published by Springer Nature in Nature
- Vol. 400 (6740), 133-137
- https://doi.org/10.1038/22055
Abstract
No abstract availableKeywords
This publication has 26 references indexed in Scilit:
- Tricritical points in random combinatorics: the -SAT caseJournal of Physics A: General Physics, 1998
- Statistical mechanics of the random-satisfiability modelPhysical Review E, 1997
- A Threshold for UnsatisfiabilityJournal of Computer and System Sciences, 1996
- Entropy of theK-Satisfiability ProblemPhysical Review Letters, 1996
- Generating hard satisfiability problemsArtificial Intelligence, 1996
- Critical Behavior in the Satisfiability of Random Boolean ExpressionsScience, 1994
- Application of statistical mechanics to NP-complete problems in combinatorial optimisationJournal of Physics A: General Physics, 1986
- The simplest spin glassNuclear Physics B, 1984
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960