I'm coming to the view that NP-complete problems are harder to work with than tasks equivalent to the halting problem.
For the halting problem, you know you're never going to solve the general case. For NP-complete problems there's a slew of complex algorithms to explore.