Comment by throwaway81523

As nullc mentioned, the simplex method can take exponential time in some pathological examples (a space of measure 0, if that matters). The first P-time linear programming algo (and proof) was the ellipsoid method of Khachian in the 1980s. I have the impression it wasn't really practical. A later P-time interior-point method by Karmarkar is used sometimes today (it beats simplex on certain types of problems) from what I understand. But, I'm nowhere near expert in this area.