Back to Search
Start Over
Constraint Satisfaction by Survey Propagation
- Source :
- Computational Complexity and Statistical Physics, Computational Complexity and Statistical Physics, 2006, 107, part 2 : 4
- Publication Year :
- 2006
- Publisher :
- HAL CCSD, 2006.
-
Abstract
- Survey Propagation is an algorithm designed for solving typical instances of random constraint satisfiability problems. It has been successfully tested on random 3-SAT and random $G(n,\frac{c}{n})$ graph 3-coloring, in the hard region of the parameter space. Here we provide a generic formalism which applies to a wide class of discrete Constraint Satisfaction Problems.<br />8 pages, 5 figures
- Subjects :
- FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Computer Science - Computational Complexity
[PHYS.COND.CM-GEN] Physics [physics]/Condensed Matter [cond-mat]/Other [cond-mat.other]
[PHYS.COND.CM-GEN]Physics [physics]/Condensed Matter [cond-mat]/Other [cond-mat.other]
FOS: Physical sciences
[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]
Disordered Systems and Neural Networks (cond-mat.dis-nn)
Computational Complexity (cs.CC)
Condensed Matter - Disordered Systems and Neural Networks
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Computational Complexity and Statistical Physics, Computational Complexity and Statistical Physics, 2006, 107, part 2 : 4
- Accession number :
- edsair.doi.dedup.....d1cfe2fe2adf83b1bbd9a3b158bc30df