Comment by throwaway81523
Comment by throwaway81523 2 days ago
Even continuous linear programming wasn't known to be in P-time until the 1980s or so.
Comment by throwaway81523 2 days ago
Even continuous linear programming wasn't known to be in P-time until the 1980s or so.
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.
The parent comment doesn't seem to be versed in complexity theory, so I tried to keep it simple.
But I think the simplex method is much older. Apparently, it dates back to 1947. Why do say it wasn't known until the 80s? Are we talking about different things?