3 ms·
SAT solvers and neural networks are probably the most curious software technologies around. Both attempt to solve NP-complete problems (learning and SAT). Both
by pron 10y ago
SAT solvers and neural networks are probably the most curious software technologies around. Both attempt to solve NP-complete problems (learning and SAT). Both are still largely based on 1960s algorithms (backpropagation for NNs and DPLL for SAT) made surprisingly useful in practice by advances in hardware and heuristics accumulated over the years. Both are mysterious from a theoretical point of view, with little progress in our theoretical understanding of why they work well in practice and how we can come up with better algorithms.
This article by Moshe Vardi[1] and this one by Dick Lipton[2] are a nice introduction to the mystery of SAT solvers.
[1]: http://cacm.acm.org/magazines/2014/3/172516-boolean-satisfiability/fulltext http://cacm.acm.org/magazines/2014/3/172516-boolean-satisfia...
[2]: https://rjlipton.wordpress.com/2009/07/13/sat-solvers-is-sat-hard-or-easy/ https://rjlipton.wordpress.com/2009/07/13/sat-solvers-is-sat...