News for hackers. Stuff that matters.
Re:After almost 20 years, math problem falls by dododo on Tuesday July 19, 2011 @05:10AM (#2780094)
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).

Re:After almost 20 years, math problem falls by mturmon on Tuesday July 19, 2011 @02:34PM (#2782388)
Yes, 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...

(expand out the "show more" button). Of course, there has been more progress since, but this summary is pretty good.