Given a linear program, by experimentation, I can see that the solver can solve large instances in a few seconds. How can I prove that my LP is in polynomial time, or can we say that it is just by experimentation?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
I have not seen anyone proving something like that.
-
$\begingroup$ So, How we can say that a given linear program is polynomial-time solvable? $\endgroup$ Dec 12, 2021 at 20:29
-
7$\begingroup$ Linear programming is in P en.wikipedia.org/wiki/… All linear programs can be solved in polynomial time $\endgroup$– fontanfDec 12, 2021 at 20:41