2
$\begingroup$

Say a problem is SPT iff it admits an SPT algorithm. What statements of interest are known to be equivalent to "LP is SPT"? Examples:

Are there others? I'd be especially interested in knowing if there are any examples that are purely "discrete" or "combinatorial" in flavor, e.g. "X is [complexity class]" (not SPT and without reference to real numbers).

Counterexamples:

  • This paper says "it is open whether 2-commodity flow and linear programming are equivalent in strongly polynomial time".
Improve this question
$\endgroup$

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.