4 ms·

Linear programming is not NP-hard and has a variety of solutions that are polynomial time [0]. It gives me pause when people say some NP-hard problem is easy in

Linear programming is not NP-hard and has a variety of solutions that are polynomial time [0]. It gives me pause when people say some NP-hard problem is easy in the "average" case without talking about what the distribution is. [0] https://en.wikipedia.org/wiki/Linear_programming#Interior_point https://en.wikipedia.org/wiki/Linear_programming#Interior_po...

pjscott 6y ago
Integer linear programming is NP-hard, which may have caused the confusion here.
- Animats 6y ago
  The classic simplex method for real linear programming is exponential-time in worst case, but cubic time in the average case. Newer algorithms can beat that.