3 ms·
Survey Propagation is one of the best algorithms for solving very hard SAT instances. Here's a good review paper that captures it. http://www.cs.cornell.edu/~
by theGnuMe 4y ago
Survey Propagation is one of the best algorithms for solving very hard SAT instances.
Here's a good review paper that captures it.
http://www.cs.cornell.edu/~sabhar/publications/surveyPropUAI07b.pdf http://www.cs.cornell.edu/~sabhar/publications/surveyPropUAI...
- AxEy 4y agoThanks
- YorkshireSeason 4y agoSurvey propagation works primarily with random SAT instances, but isn't competitive with SAT instances that arise in industrial verification, where CDCL shines. Some gossip: survey propagation was proposed by Mezard, Parisi, and Zecchina [1], and G. Parisi won the physics Nobel price in 2021 [2]. [1] M. Mezard, G. Parisi, R. Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems. https://aiichironakano.github.io/cs653/Mezard-RSAT-Science02.pdf https://aiichironakano.github.io/cs653/Mezard-RSAT-Science02... [2] https://en.wikipedia.org/wiki/Giorgio_Parisi https://en.wikipedia.org/wiki/Giorgio_Parisi