4 ms·
Hmm, the above poster probably meant "linear programming with integers" being NP-hard (because it is). When its "smooth", its actually solvable in polynomial t
by dragontamer 4y ago
Hmm, the above poster probably meant "linear programming with integers" being NP-hard (because it is).
When its "smooth", its actually solvable in polynomial time.
- Animats 4y agoRight, see [1]. Same concept, though - worst case far harder than the average case, and the worse case is rare. [1] https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency_in_the_worst_case https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency_i...