For sure: a traveling salesman route under length L, for instance. But what is good enough when combining incompatible people? Less than three vendettas per table? :)
The trick is that some types of problems, like TSP or assignment problems, have structure that can be exploited. Of course they remain NP-hard, so as size grows, at some point the computational cost becomes unsustainable. But the point at which this happens is often way further (i.e. for much larger instances) than most imagine.
For sure: a traveling salesman route under length L, for instance. But what is good enough when combining incompatible people? Less than three vendettas per table? :)
I agree with grandparent that non-optimal solutions are often enough.
But just to be complete, since TSP was mentioned here:
We could solve TSP instances with >80k cities to optimality back in 2006:
https://www.math.uwaterloo.ca/tsp/
The trick is that some types of problems, like TSP or assignment problems, have structure that can be exploited. Of course they remain NP-hard, so as size grows, at some point the computational cost becomes unsustainable. But the point at which this happens is often way further (i.e. for much larger instances) than most imagine.