<p>It depends on the answer. If the algorithm created has running time $(d n)^{Ackerman(10000)}$, then it would have very little impact. On the other hand, if it leads to a new way to solve LPs it might have tremendous impact. For example, if I remember the history correctly (and I might be <em>completely wrong</em>) the ellipsoid algorithm for example, besides its theoretical significance, lead (?) to the development of the interior point method, which was faster in some cases than the simplex algorithm. This lead to significant speedup in practice, as both approaches were squeezed for the maximum limit of what can be done.</p>

CC BY-SA 2.5
2010-10-13T20:42:37.700Z
But these conditions hold for pretty much any theoretical result: it may or may not be useful depending on the runtime, and the techniques/ideas in the result may lead to future advances.
Ian
CC BY-SA 2.5
2010-10-13T21:17:30.240Z
Not really. If some form of the Hirsch conjecture is true, and the proof is constructive, then it would almost surely lead to faster solvers for LP. In short, if the question is specific then its implications are clear, and if the question is wide then it might lead to nothing. Or putting it differently, the only sure consequence of polynomial time algorithm for LP is that we would understand the problem better than we do now.
Sariel Har-Peled
CC BY-SA 2.5
2010-10-13T04:00:44.597Z
2010-10-13T04:00:44.597Z
Sariel Har-Peled
<p>Here is one consequence for geometry : A strongly-polynomial bound for any variant (randomized or deterministic) of simplex algorithm implies a polynomial bound on the diameter of any polytope graph. This implies that the "polynomial version" of <a href="http://en.wikipedia.org/wiki/Hirsch_conjecture" rel="nofollow">Hirsch conjecture</a> is true.</p>

CC BY-SA 2.5
2010-10-13T02:08:35.737Z
but there's no reason to believe that a strongly polynomial time algorithm for LPs has to go via the simplex method. The best known methods thus far (subexponential) use a random samping+recursion strategy.
Suresh Venkat
CC BY-SA 2.5
2010-10-13T02:13:58.883Z
Oops. I missed the point.
Shiva Kintali
CC BY-SA 2.5
2010-10-13T02:31:40.057Z
This only holds if simplex is strongly polynomial.  I'm looking for results that hold more generally.  It could be that the polynomial Hirsch conjecture is false but another algorithm is strongly polynomial, or that the polynomial Hirsch conjecture is true but simplex is exponential because it cannot find a short path in polynomial time.
Ian
CC BY-SA 2.5
2010-10-13T03:24:00.767Z
@Suresh: Actually, I'm pretty sure the subexponential random sampling + recursion strategy you mention (Clarkson-Matoušek-Sharir-Welzl/Kalai, right?) *is* a dual simplex algorithm.  (But this doesn't contradict your point.)
Jeffε
CC BY-SA 2.5
2010-10-13T03:43:00.713Z
oh wait. Didn't Michael Goldwasser work that out a long time ago in a SIGACT article ? Hmm. now I need to go and dig.
Suresh Venkat
CC BY-SA 2.5
2010-10-13T02:04:27.313Z
2010-10-13T02:04:27.313Z
Shiva Kintali
<p>This would show that parity and mean-payoff games are in P. See <a href="http://www.csc.liv.ac.uk/~sven/mfcs09.pdf">Sven Schewe. From Parity and Payoff Games to Linear Programming. MFCS 2009. </a></p>

CC BY-SA 4.0
2022-10-27T22:49:16.547Z
What about the converse?
user76284
CC BY-SA 2.5
2010-10-13T22:33:44.623Z
excellent. I wish I could give this more than one +1. this is a very cool result.
Suresh Venkat
CC BY-SA 2.5
2010-10-14T19:56:29.427Z
Could someone elaborate how a strongly polynomial algorithm for LP would imply this? Schewe builds a polynomial-size instance of LP with doubly exponentially big numbers. Fine. Now we run the strongly polynomial time algorithm on it. But don't we need to simulate the arithmetic operations that this algorithm makes? How is this simulation done without spending super-polynomial time? (recall the numbers are doubly exponential; I guess one could do Chinese remainder trick, but can we do comparison of numbers this way in polynomial time?).
slimton
CC BY-SA 2.5
2010-10-14T22:52:20.697Z
I haven't read the paper carefully yet, but as I understand it they're only proving the problem is in P in the Real RAM/BSS model (http://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine), not the normal version of P.  You can define models of computation over any ring R (see http://www.ams.org/notices/200409/fea-blum.pdf).  Over $\mathbb{Z}_2$ we get normal Turing Machines, and over the reals $\mathbb{R}$ we get the BSS model.  Each ring has its own version of P, which may not be equal to the standard P.
Ian
CC BY-SA 2.5
2010-10-14T23:17:41.423Z
Clarification to my previous comment: if there is a strongly polynomial algorithm for LP, then it is polynomial in the BSS model, in which case the paper implies parity and payoff games are also in P in the BSS model.
Ian
CC BY-SA 2.5
2010-10-15T19:12:59.133Z
@Ian: In other words: this answer was a bit misleading (but that didn't stop you from accepting it as valid answer).
slimton
CC BY-SA 2.5
2010-10-19T09:22:24.517Z
@slimton, @Ian: my response is based on the definition of strongly polynomial in the original question - "runtime is bounded by a polynomial in the number of variables and constraints and is independent of the size of the representation of the parameters". Given that, do you believe my answer is still misleading?
Rahul Savani
CC BY-SA 2.5
2010-10-23T04:40:09.293Z
@Rahul: I think this is an interesting result, and I don't think your answer was misleading.  I actually neglected to give the full definition of strongly polynomial in the question: the number of arithmetic operations should be bounded by a polynomial in the number of parameters (which makes it poly in BSS) *and* it needs to use polynomial space on a Turing machine, so no doubly-exponential numbers like this paper uses.  A polynomial algorithm for LPs in the BSS model would still be a big deal, though.
Ian
CC BY-SA 2.5
2010-10-13T22:27:28.850Z
2010-10-13T22:54:07.217Z
2010-10-13T22:54:07.217Z
Rahul Savani
<p>One of the holy grails of algorithm design is finding a <em>strongly polynomial</em> algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and constraints and is independent of the size of the representation of the parameters (assuming unit cost arithmetic).  Would resolving this question have implications outside of better algorithms for linear programming?  For instance, would the existence/non-existence of such an algorithm have any consequences for geometry or complexity theory?</p>

<p><strong>Edit:</strong> Maybe I should clarify what I mean by consequences.  I'm looking for mathematical consequences or conditional results, implications that are known to be true <em>now</em>.  For instance: "a polynomial algorithm for LP in the BSS model would separate/collapse algebraic complexity classes FOO and BAR", or "if there is no strongly polynomial algorithm then it resolves such-and-such conjecture about polytopes", or "a strongly polynomial algorithm for problem X which can be formulated as an LP would have interesting consequence <em>blah</em>".  The Hirsch conjecture would be a good example, except that it only applies if simplex is polynomial.</p>

CC BY-SA 2.5
2010-10-13T04:14:55.683Z
it also goes without saying that the proof technique used to show this result might be even more interesting than the result in terms of long-term impact.
Suresh Venkat
<ds.algorithms><conditional-results><linear-programming><computing-over-reals><simplex>
Consequences of existence of a strongly polynomial algorithm for linear programming?
Ian
# Consequences of existence of a strongly polynomial algorithm for linear programming?

(Asked by: username_0 on 2010-10-13)

One of the holy grails of algorithm design is finding a *strongly polynomial* algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and constraints and is independent of the size of the representation of the parameters (assuming unit cost arithmetic). Would resolving this question have implications outside of better algorithms for linear programming? For instance, would the existence/non-existence of such an algorithm have any consequences for geometry or complexity theory?

**Edit:** Maybe I should clarify what I mean by consequences. I'm looking for mathematical consequences or conditional results, implications that are known to be true *now*. For instance: "a polynomial algorithm for LP in the BSS model would separate/collapse algebraic complexity classes FOO and BAR", or "if there is no strongly polynomial algorithm then it resolves such-and-such conjecture about polytopes", or "a strongly polynomial algorithm for problem X which can be formulated as an LP would have interesting consequence *blah*". The Hirsch conjecture would be a good example, except that it only applies if simplex is polynomial.

**Tags:** ds.algorithms, conditional-results, linear-programming, computing-over-reals, simplex
> **Comments:**
> **username_1**: it also goes without saying that the proof technique used to show this result might be even more interesting than the result in terms of long-term impact.  

---

## 3 answers

### Answer by username_5 on 2010-10-13. Score: 29 | Accepted answer

This would show that parity and mean-payoff games are in P. See [Sven Schewe. From Parity and Payoff Games to Linear Programming. MFCS 2009.](http://www.csc.liv.ac.uk/~sven/mfcs09.pdf)

> **Comments:**
> **username_1**: excellent. I wish I could give this more than one +1. this is a very cool result.  
> **username_7**: Could someone elaborate how a strongly polynomial algorithm for LP would imply this? Schewe builds a polynomial-size instance of LP with doubly exponentially big numbers. Fine. Now we run the strongly polynomial time algorithm on it. But don't we need to simulate the arithmetic operations that this algorithm makes? How is this simulation done without spending super-polynomial time? (recall the numbers are doubly exponential; I guess one could do Chinese remainder trick, but can we do comparison of numbers this way in polynomial time?).  
> **username_0**: I haven't read the paper carefully yet, but as I understand it they're only proving the problem is in P in the Real RAM/BSS model (http://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine), not the normal version of P.  You can define models of computation over any ring R (see http://www.ams.org/notices/200409/fea-blum.pdf).  Over $\mathbb{Z}_2$ we get normal Turing Machines, and over the reals $\mathbb{R}$ we get the BSS model.  Each ring has its own version of P, which may not be equal to the standard P.  
> **username_0**: Clarification to my previous comment: if there is a strongly polynomial algorithm for LP, then it is polynomial in the BSS model, in which case the paper implies parity and payoff games are also in P in the BSS model.  
> **username_7**: @Ian: In other words: this answer was a bit misleading (but that didn't stop you from accepting it as valid answer).  
> **username_5**: @slimton, @Ian: my response is based on the definition of strongly polynomial in the original question - "runtime is bounded by a polynomial in the number of variables and constraints and is independent of the size of the representation of the parameters". Given that, do you believe my answer is still misleading?  
> **username_0**: @Rahul: I think this is an interesting result, and I don't think your answer was misleading.  I actually neglected to give the full definition of strongly polynomial in the question: the number of arithmetic operations should be bounded by a polynomial in the number of parameters (which makes it poly in BSS) *and* it needs to use polynomial space on a Turing machine, so no doubly-exponential numbers like this paper uses.  A polynomial algorithm for LPs in the BSS model would still be a big deal, though.  
> **username_6**: What about the converse?  

---

### Answer by username_2 on 2010-10-13. Score: 8

It depends on the answer. If the algorithm created has running time $(d n)^{Ackerman(10000)}$, then it would have very little impact. On the other hand, if it leads to a new way to solve LPs it might have tremendous impact. For example, if I remember the history correctly (and I might be *completely wrong*) the ellipsoid algorithm for example, besides its theoretical significance, lead (?) to the development of the interior point method, which was faster in some cases than the simplex algorithm. This lead to significant speedup in practice, as both approaches were squeezed for the maximum limit of what can be done.

> **Comments:**
> **username_0**: But these conditions hold for pretty much any theoretical result: it may or may not be useful depending on the runtime, and the techniques/ideas in the result may lead to future advances.  
> **username_2**: Not really. If some form of the Hirsch conjecture is true, and the proof is constructive, then it would almost surely lead to faster solvers for LP. In short, if the question is specific then its implications are clear, and if the question is wide then it might lead to nothing. Or putting it differently, the only sure consequence of polynomial time algorithm for LP is that we would understand the problem better than we do now.  

---

### Answer by username_3 on 2010-10-13. Score: 5

Here is one consequence for geometry : A strongly-polynomial bound for any variant (randomized or deterministic) of simplex algorithm implies a polynomial bound on the diameter of any polytope graph. This implies that the "polynomial version" of [Hirsch conjecture](http://en.wikipedia.org/wiki/Hirsch_conjecture) is true.

> **Comments:**
> **username_1**: but there's no reason to believe that a strongly polynomial time algorithm for LPs has to go via the simplex method. The best known methods thus far (subexponential) use a random samping+recursion strategy.  
> **username_3**: Oops. I missed the point.  
> **username_0**: This only holds if simplex is strongly polynomial.  I'm looking for results that hold more generally.  It could be that the polynomial Hirsch conjecture is false but another algorithm is strongly polynomial, or that the polynomial Hirsch conjecture is true but simplex is exponential because it cannot find a short path in polynomial time.  
> **username_4**: @Suresh: Actually, I'm pretty sure the subexponential random sampling + recursion strategy you mention (Clarkson-Matoušek-Sharir-Welzl/Kalai, right?) *is* a dual simplex algorithm.  (But this doesn't contradict your point.)  
> **username_1**: oh wait. Didn't Michael Goldwasser work that out a long time ago in a SIGACT article ? Hmm. now I need to go and dig.  

---

