> This is true in principle, but the reality is more complicated. When we say “NP-complete is hard” we’re talking about worst-case complexity, and the average-case complexity is often much more tractable. Many industry problems are “well-behaved” and modern SAT solvers can solve them quickly.
This is a really cool point, no one ever mentioned this to me when I learned about this stuff at university. I wonder though, is there data for this ? Are businesses willing to take the risk and how do they mitigate ?
I'm not sure how popular they are in the wild, but there are a lot of approximation algorithms as well for solving version of these problems that are almost-but-not-quite the same. I wonder if that's just what lots of real-world use cases actually need.
This is a really cool point, no one ever mentioned this to me when I learned about this stuff at university. I wonder though, is there data for this ? Are businesses willing to take the risk and how do they mitigate ?
I'm not sure how popular they are in the wild, but there are a lot of approximation algorithms as well for solving version of these problems that are almost-but-not-quite the same. I wonder if that's just what lots of real-world use cases actually need.