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:
- "linear feasibility solving is SPT" (due to the strong duality theorem)
- "solving zero-sum games is SPT" (see here)
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".