Re:Chasing a Bug in a SAT Solver
by cjfd on Friday June 21, 2024 @05:00AM
(#40747601)
Maybe one could attempt to use a proof assistant to prove that the algorithm is correct?
[ Parent
| on HN ]
Re:Chasing a Bug in a SAT Solver
by JonChesterfield on Friday June 21, 2024 @07:39AM
(#40748503)
For what it's worth I'm now working on a proof assistant so yeah, that's the game plan. I think the straight line case for the solver is probably OK but there's a huge range of optimisations out there and it's far too easy to introduce errors there.
Re:Chasing a Bug in a SAT Solver
by CJefferson on Friday June 21, 2024 @06:42AM
(#40748129)
At present we are a long way from proving general constraint solvers are correct, as they are built from some many little algorithms that interact in weird ways.
It's an interesting area, and I hope we'll get there in the future.
Re:Chasing a Bug in a SAT Solver
by nextaccountic on Friday June 21, 2024 @06:21AM
(#40748033)
Or just prove yourself with pen and paper if the algorithm works, using structural induction and other techniques. Then it's just a matter of whether the code follows the spec