3 ms·
I think it's famous because it's one of the most easily understandable NP-complete problems: it has a nice, intuitive "word problem" description. 3SAT has no su
by geofft 11y ago
I think it's famous because it's one of the most easily understandable NP-complete problems: it has a nice, intuitive "word problem" description. 3SAT has no such intuitive description. Even for those of us who understand boolean formulas, there's no particular intuition about how hard 3SAT (and 2SAT) should be. It's a fairly abstract mathematical construct.
NP-complete problems admit no polynomial-time solution for every possible answer, and even if they run in more-than-polynomial time, there's no constraint on what those constants look like. Suppose the best algorithm takes 2^n / 2^100000 seconds. That's definitely more than polynomial, but also pretty fast for real-world problem sizes.
It turns out that even SAT solvers are also pretty good in practice on real-world-sized problems, to the point where Fedora's and SUSE's dependency solvers (in dnf and zypper, respectively) convert your package dependencies to an instance of SAT and throw it at a generic SAT solver, because that's better-optimized.