6 ms·
for linear programming there are several well known polynomial time algorithms (some interior point methods: ellipsoid, projective, etc)--the problem itself is
by dododo 15y ago
for linear programming there are several well known polynomial time algorithms (some interior point methods: ellipsoid, projective, etc)--the problem itself is by no means in EXP or NP.
for worst case complexities it's often just a small region of the problem space that makes the bound large--but enumerating or cutting out those cases is tricky. you just don't see them on average because they are few (c.f., quicksort: O(n^2) worst case, O(n log n) average).
- mturmon 15y agoYes, here's a summary (somewhat dated) of this, given in a prize award for one of the key people who showed that worst-case is rare: http://www.informs.org/Recognize-Excellence/Award-Recipients/Karl-Heinz-Borgwardt http://www.informs.org/Recognize-Excellence/Award-Recipients... (expand out the "show more" button). Of course, there has been more progress since, but this summary is pretty good.