This has been known for a while now, and I would suggest it's not so much about "tractable" vs "intractable" problem classes. It's important to understand what

This has been known for a while now, and I would suggest it's not so much about "tractable" vs "intractable" problem classes. It's important to understand what NP-hard means -- it doesn't mean exponential complexity, but worst case exponential complexity (a theoretical bound). It means there's always the possibility we will hit the worst case, but it doesn't mean we always do. If you exploit structure and apply heuristics, you can achieve very good average case performance. In fact, we have been solving NP-hard problems in mission-critical environments quite efficiently for many years now. Take the case of Mixed Integer Linear Programs (MILP) -- that is, Linear Programs (LPs) with integer variables. It is well known that they are NP-hard. However, modern solvers (CPLEX, Gurobi) implement a whole bunch of heuristics and techniques that make solver performance extremely good on most problems. MILPs are used to do large-scale planning, routing, etc. and industry relies on MILP solutions every day. MILP solvers today are 10^9 times faster than in 1991, and most of that speedup owes firstly to algorithmic breakthroughs, and secondly to machine improvements. It's astounding. https://www.fields.utoronto.ca/programs/scientific/11-12/bc65/rbixby.pdf https://www.fields.utoronto.ca/programs/scientific/11-12/bc6... That said, MILPs remain NP-hard, which means there's always a chance you will run into cases where the solution will take exponential time to solve (full enumeration). It's an escapable property of this problem class. But the take-home is: NP-hardness does not inherently mean intractability in general.