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).


  • This paper says "it is open whether 2-commodity flow and linear programming are equivalent in strongly polynomial time".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy