33
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Oct 13, 2010 at 4:14

3 Answers 3

Reset to default
29
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ excellent. I wish I could give this more than one +1. this is a very cool result. $\endgroup$
    – Suresh Venkat
    Commented Oct 13, 2010 at 22:33
  • $\begingroup$ 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?). $\endgroup$
    – slimton
    Commented Oct 14, 2010 at 19:56
  • 2
    $\begingroup$ 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 (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 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. $\endgroup$
    – Ian
    Commented Oct 14, 2010 at 22:52
  • $\begingroup$ 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. $\endgroup$
    – Ian
    Commented Oct 14, 2010 at 23:17
  • $\begingroup$ @Ian: In other words: this answer was a bit misleading (but that didn't stop you from accepting it as valid answer). $\endgroup$
    – slimton
    Commented Oct 15, 2010 at 19:12
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Ian
    Commented Oct 13, 2010 at 20:42
  • $\begingroup$ 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. $\endgroup$
    – Sariel Har-Peled
    Commented Oct 13, 2010 at 21:17
5
$\begingroup$

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 is true.

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Oct 13, 2010 at 2:08
  • $\begingroup$ Oops. I missed the point. $\endgroup$
    – Shiva Kintali
    Commented Oct 13, 2010 at 2:13
  • $\begingroup$ 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. $\endgroup$
    – Ian
    Commented Oct 13, 2010 at 2:31
  • $\begingroup$ @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.) $\endgroup$
    – Jeffε
    Commented Oct 13, 2010 at 3:24
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Oct 13, 2010 at 3:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.