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".
$\endgroup$

0

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.