> I don't think talking about these things in absolute terms is very useful. Everything depends on the problem and the customer's expectations.

Agreed. In the real world, approximate solutions to hard problems are often good enough.

For instance, the TSP might be a hard problem, but solving it exactly is pointless since the distances between nodes might be subject to measurement uncertainty anyway, and actual travel times might not be fixed as they might fall under a distribution.

Having said that, it’s still worth studying the theoretical aspects of these problems.