This reminds me of the random polynomial time bound for the simplex algorithm; an algorithm that is, naively, exponential time[1]. I seem to vaguely remember —

This reminds me of the random polynomial time bound for the simplex algorithm; an algorithm that is, naively, exponential time[1]. I seem to vaguely remember — this is ~17 years ago, now — that it's possible to "characterize" the really bad edge-cases for simplex and work around them (the whole point of the paper). [1] https://cstheory.stackexchange.com/questions/2373/complexity-of-the-simplex-algorithm#2374 https://cstheory.stackexchange.com/questions/2373/complexity...