I think it&#x27;s famous because it&#x27;s one of the most easily understandable NP-complete problems: it has a nice, intuitive &quot;word problem&quot; description. 3SAT has no such intuitive description. Even for those of us who understand boolean formulas, there&#x27;s no particular intuition about how hard 3SAT (and 2SAT) <i>should</i> be. It&#x27;s a fairly abstract mathematical construct.<p>NP-complete problems admit no polynomial-time solution <i>for every possible answer</i>, and even if they run in more-than-polynomial time, there&#x27;s no constraint on what those constants look like. Suppose the best algorithm takes 2^n &#x2F; 2^100000 seconds. That&#x27;s definitely more than polynomial, but also pretty fast for real-world problem sizes.<p>It turns out that even SAT solvers are also pretty good in practice on real-world-sized problems, to the point where Fedora&#x27;s and SUSE&#x27;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&#x27;s better-optimized.