> Or do we lack the ability to determine whether a given instance of 3SAT is hard? Yes. At least in general. In fact, answering whether any SAT (or 3SAT) insta

> Or do we lack the ability to determine whether a given instance of 3SAT is hard? Yes. At least in general. In fact, answering whether any SAT (or 3SAT) instances are hard equivalent to settling P vs. NP. Assuming easy = polynomial, the "easy subset" of SAT = SAT iff P = NP. Separating hard from easy instances -- in general -- is pretty much the secret to complexity theory. We do know to recognize some easy cases. SAT is FPT -- i.e. fixed parameter tractable [1] -- because its worst-case solving time is exponential in the number of variables. There are more complex cases of easy instances. A question that is easier than P vs. NP is separating SAT instances that are easy/hard for DPLL (+ improvements), the 1960s algorithm at the core of all SAT solvers. AFAIK, this, too, is an unanswered question in general (i.e., given a SAT instance, we don't know how to tractably determine whether or not DPLL will tractably solve it). [1]: https://en.wikipedia.org/wiki/Parameterized_complexity#FPT https://en.wikipedia.org/wiki/Parameterized_complexity#FPT