2 ms·

Even continuous linear programming wasn't known to be in P-time until the 1980s or so.

• tgv 1y ago
  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?
  • nullc 1y ago
    The simplex algorithm is exponential in the worst case, in spite of the fact that it performs very well 'on average'.
    • tgv 1y ago
      I had always blindly assumed it was polynomial. Thanks.
  • throwaway81523 1y ago
    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.