| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
Pairs of SAT Assignments and Clustering in Random Boolean Formulae | Thierry Mora
; Marc Mezard
; Riccardo Zecchina
; | Date: |
2 Jun 2005 | Subject: | Disordered Systems and Neural Networks; Computational Complexity | cond-mat.dis-nn cs.CC | Affiliation: | LPTMS), Marc Mezard (LPTMS), Riccardo Zecchina (ICTP | Abstract: | We investigate geometrical properties of the random K-satisfiability problem. For large enough K, we prove that there exists a region of clause density, below the satisfiability threshold, where SAT assignments are grouped into well separated clusters. This confirms the validity of the clustering scenario which is at the heart of the recent heuristic analysis of satisfiability using statistical physics analysis (the cavity method), and its algorithmic counterpart (the survey propagation algorithm). Our method relies on the study of pairs of SAT-assignments at a fixed distance. It uses elementary probabilistic arguments (first and second moment methods), and might be useful in other problems of computational and physical interest where similar phenomena appear. | Source: | arXiv, cond-mat/0506053 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |