Name
Abstract | ||
|---|---|---|
Using elementary rigorous methods we prove the existence of a clustered phase in the random K-SAT problem, for K >= 8. In this phase the solutions are grouped into clusters which are far away from each other. The results are in agreement with previous predictions of the cavity method and give a rigorous confirmation to one of its main building blocks. It can be generalized to other systems of both physical and computational interest. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1103/PhysRevLett.94.197205 | PHYSICAL REVIEW LETTERS |
Keywords | Field | DocType |
numerical simulation,satisfiability,spin glass | Statistical physics,Cluster (physics),Boolean satisfiability problem,Cavity method,Cluster analysis,Condensed matter physics,Physics | Journal |
Volume | Issue | ISSN |
94 | 19 | 0031-9007 |
Citations | PageRank | References |
53 | 3.11 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marc Mézard | 1 | 590 | 39.09 |
| thierry mora | 2 | 53 | 3.11 |
| riccardo zecchina | 3 | 637 | 55.46 |