The catch here is that P vs NP talks about worst-case behavior. Many SAT solver inputs can be solved quickly with good heuristics, but there are some that are s

The catch here is that P vs NP talks about worst-case behavior. Many SAT solver inputs can be solved quickly with good heuristics, but there are some that are still difficult no matter what you do. One way to see this is via the phase transition behavior of SAT. https://www.researchgate.net/profile/Lavallee-Ivan/publication/36444542/figure/fig1/AS:309948492861441@1450908887802/Phase-transition-of-satisfiability-probability-in-3-SAT-around-a-c.png https://www.researchgate.net/profile/Lavallee-Ivan/publicati... If you have too few constraints it's easy to find a solution to the problem. If there are too many constraints it's also easy to show there are no solutions. But in the middle there's a sweet spot in the ratio of constraints to variables that's when the problem becomes fiendishly difficult.