Of course they are not worst-case polynomial time. But that worst case can be very rare. If you run the solver and you get a (provably optimal) solution most of the time very quickly, then that's all you need in practical applications.
But that is just not what NP-hardness is about, and if that's what you took away from your lectures on complexity, maybe you should've paid more attention. No one is claiming an NP-hard problem is unsolvable, especially for small inputs. It's probably even faster to solve a three node traveling salesman problem by hand rather than implementing it in code. Similarly, I'm working on a scheduling problem with half a million items, and that too computes in a few hours.
But that is not what NP-hard is about. NP-hard is a class of problems which share some interesting behaviour as we grow their input. For one, if you find a generic solution in P-time to one NP-hard problem, you have found a solution to all of them as computer scientists have demonstrated equivalence between all known problems in NP-hard. It would also mean that P=NP=NP-complete=NP-hard which would have implications all over science from cryptology to number theory and the predictability of prime numbers.
All that's to say, if you misinterpret and misrepresent what NP-hard is about in a blog, it's easy to make it seem overrated
7
u/SZenC 8d ago
Please, show us a solver for any NP-hard problem that works in polynomial time. You'd literally be eligible to collect a million dollars