3 ms·
In the same sense that SQL is a universal way of expressing a large set of problems. I.e. all the implementations speak the same language, but they operate and
by everforward 3y ago
In the same sense that SQL is a universal way of expressing a large set of problems.
I.e. all the implementations speak the same language, but they operate and prioritize differently.
SAT solvers are NP-Hard, so there isn't a single SAT solver to rule them all. Which one you choose matters, same as with databases. CockroachDB, PostgreSQL and SQLite all speak SQL, but are not interchangeable. Same with SAT solvers.
I'd agree with OP; the SAT writers should get more credit. It's a hard problem, and I'd bet most of us are either incapable or unwilling to spend ages working on it (myself included, no shade intended). It's also vitally important. To my understanding, SAT solvers underly most package managers. It's how npm or pip or apt know what version to install for each package such that no version violates another packages constraints (if any, it's also where the "no valid version combinations exist" message comes from).
- Sesse__ 3y agoapt doesn't use a SAT solver; it has its own heuristics. (Seemingly it _can_ call out to an external one if you give the --solver argument, which in 20+ years of Debian I have never seen anyone use, and which I didn't know of before I made a search now to make sure.)
- everforward 3y agoOh, that's interesting, thanks for the correction! Now I have some reading material for when I'm bored. I'm curious how they handle it without a SAT solver.