Hacker News new | past | comments | ask | show | jobs | submit login
Empirical Study of the Anatomy of Modern SAT Solvers (2011) [pdf] (toronto.edu)
95 points by luu on April 8, 2017 | hide | past | favorite | 2 comments

Donald Knuth recently released the latest chapter of 'The Art of Computer Programming' and decided to tackle the topic of Satisfiability & SAT solvers ( @ https://www.amazon.com/Art-Computer-Programming-Fascicle-Sat... ). Although he refers to algorithms in an vague way (using words like "Algorithm A" or "Algorithm J") and makes a determined effort to convey all information in the most mathematically precise way possible, I'm of the view that it's the finest work of it's kind on this topic. Having a section on something like 'random restarts' is great, but if you are already deep enough to have an interest in a paper like this, you are deep enough to learn about Luby sequences.

Kevin Leyton-Brown's research is a good read for SAT if you're interested in the state-of-the-art, and more specifically emperical/meta algorithms: http://www.cs.ubc.ca/~kevinlb/publications.html

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact