News for hackers. Stuff that matters.
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?
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