Re:The undeserved status of the pigeon-hole principle (1991)
by andrepd on Saturday July 04, 2020 @07:56PM
(#23735720)
SAT solvers overwhelmingly don't use resolution. Modern state of the art solvers use DPLL/CDCL.
[ Parent
| on HN ]
Re:The undeserved status of the pigeon-hole principle (1991)
by 53x15 on Saturday July 04, 2020 @08:52PM
(#23735912)
I think neel_k was referring to the fact that when a DPLL or CDCL solver concludes UNSAT you can take the trace its backtracking activity and rewrite it from the bottom up as a resolution refutation. So in this sense the solvers are finding resolution proofs.
Re:The undeserved status of the pigeon-hole principle (1991)
by CJefferson on Sunday July 05, 2020 @05:05AM
(#23737476)
While they indeed don't use resolution directly, DPLL/CDCL is in many ways equivalent.
Most modern SAT solvers will still have trouble with the pigeon-hole style problems (although some have inbuilt explicit detection, or symmetry breaking, which will let them solve it efficiently).