The simplex method is an algorithm for solving LPs; the comparison of a particular algorithm's running time to the complexity of a problem isn't exactly one-to-

The simplex method is an algorithm for solving LPs; the comparison of a particular algorithm's running time to the complexity of a problem isn't exactly one-to-one. In this particular case, there are algorithms with polynomial-time worst-case guarantees for solving the same problem as simplex, including the classical ellipsoid method and a whole battery of interior point methods. The only technique complexity theorists have at the moment for finding unconditional lower bounds for a problem's running time is diagonalization, as in the method used for proving the time hierarchy theorem. While this can be used to prove that some problems require exponential time to solve, it is provably too weak to separate P from PSPACE, let alone P from NP. But it is enough to separate P from EXPTIME, meaning that any EXPTIME-hard problem such as Generalized Chess is provably not in P. The point you touch on with Simplex is interesting, because as you mentioned it works extremely well in practice despite the well-studied lower bounds. There is some line of work that tries to explain it with "Smoothed Complexity" analysis, but despite the polynomial bound the current results are still not terribly satisfying. More generally, I think you were hypothesizing something along the lines of Imagliazzo's "Heuristica" (see https://gilkalai.wordpress.com/2008/11/12/impagliazzos-multiverse/ https://gilkalai.wordpress.com/2008/11/12/impagliazzos-multi... ), where NP-hard problems are hard in the worst case but actually finding these hard instances is equally difficult. This is a very real scenario, with both pros (we can solve stuff!) and cons (hackers can too!), at least on a theoretical level where "solvable" is synonymous with "polynomial time solvable". I think this is considered the third most likely of the five hypothesized worlds after Cryptomania and Mini-crypt.