3 ms·
> linear programming are problems that are worst-case NP-hard Linear Programming (with rational coefficients; to avoid sophism) can be solved in polynomial tim
by aleph_minus_one 4y ago
> linear programming are problems that are worst-case NP-hard
Linear Programming (with rational coefficients; to avoid sophism) can be solved in polynomial time.
- dragontamer 4y agoHmm, 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...