4 ms·
The wording is a tiny bit misleading because assuming P ≠ NP, then the set of SAT problems that SAT solvers can solve in polynomial time is, by definition, in P
by pron 4y ago
The wording is a tiny bit misleading because assuming P ≠ NP, then the set of SAT problems that SAT solvers can solve in polynomial time is, by definition, in P and not NP-hard (if they were, then, again, by definition of NP-hard, we could reduce all of the problems in NP to those in that set, proving P = NP, contrary to our assumption). I.e. assuming that there's a subset of SAT that SAT solvers can solve -- of any problem size -- in polynomial time, then that subset is not NP-complete. SAT is still NP-hard (and NP complete), because we can reduce any problem in NP to SAT, but not to that "easy" subset. It's just that the mystery, as Hillel alludes, is that we don't yet know how to classify that subset so it doesn't have a name.
In other words, it's not that NP-complete isn't always hard; assuming P ≠ NP -- it is. It's just that (in addition to obvious subclasses of SAT) there's a non-obvious subclass of SAT that's in P that SAT solvers can solve (again, assuming they actually solve all of the problems in that class in polynomial time) that we have yet to classify, and it is, indeed, an interesting mystery.