4 ms·
I'm afraid I was not familiar, although I'm looking at a few related papers on the arxiv now. What brought that approach to mind?
by AxEy 4y ago
I'm afraid I was not familiar, although I'm looking at a few related papers on the arxiv now.
What brought that approach to mind?
- theGnuMe 4y agoSurvey 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