|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Simplest random K-satisfiability problem | | F. Ricci-Tersenghi
; M. Weigt
; R. Zecchina
; | | Date: |
10 Nov 2000 | | Journal: | Phys. Rev. E 63, 026702 (2001) | | Subject: | Disordered Systems and Neural Networks; Statistical Mechanics; Computational Complexity | cond-mat.dis-nn cond-mat.stat-mech cs.CC | | Abstract: | We study a simple and exactly solvable model for the generation of random satisfiability problems. These consist of $gamma N$ random boolean constraints which are to be satisfied simultaneously by $N$ logical variables. In statistical-mechanics language, the considered model can be seen as a diluted p-spin model at zero temperature. While such problems become extraordinarily hard to solve by local search methods in a large region of the parameter space, still at least one solution may be superimposed by construction. The statistical properties of the model can be studied exactly by the replica method and each single instance can be analyzed in polynomial time by a simple global solution method. The geometrical/topological structures responsible for dynamic and static phase transitions as well as for the onset of computational complexity in local search method are thoroughly analyzed. Numerical analysis on very large samples allows for a precise characterization of the critical scaling behaviour. | | Source: | arXiv, cond-mat/0011181 | | Other source: | [GID 595574] pmid11308607 | | 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 Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER