> If you're solving some problem quickly, then we know that what you've solved was not one of the hard problems to begin with. If you're solving some problems in polynomial time, then those problems are in P.

I thought complexity classes applied to the problem definition, not the specific instances of the problem? An easy SAT problem instance doesn't belong in any complexity class, the set of SAT problem instances belongs to NP.

Yes, we must parameterise problems to meaningfully talk about classes [1], but interesting algorithms are interesting because they tractably give an answer to some large set of inputs. Their authors may not always know how to meaningfully parameterise the full set of inputs that they solve efficiently, but if they're interesting, then there's some implied set that could be parameterised.

But this is less handwavy than this may sound because SAT solvers don't actually solve "the SAT problem" efficiently. Rather, they make guesses about true/false assignments to particular SAT variables, and the algorithm knows when a guess is successful and when it isn't, because when it makes a wrong guess it backtracks (i.e. it knowingly takes a step that could be said to be "exponential"). Over the entire set of SAT problems of a particular length, every guess will still be right some of the time and wrong (leading to a backtrack) some of the time. Yet the utility of these solvers comes from them making good guesses more than half the time. That means that there must be something special about the set of problems that they can solve with a smaller-than-expected number of backtracks.

Put another way, every solver algorithm could be presented with specific instances, of any size, where the number of backtracks is small or large.

[1]: This makes the notion of circuit complexity a challenging, hence the notion of "uniformity": https://en.wikipedia.org/wiki/Circuit_complexity#Uniformity