Hacker News Reader

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/surveyPropUAI...

Survey 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...

[2] https://en.wikipedia.org/wiki/Giorgio_Parisi

Thanks

Reply on news.ycombinator.com