Conséquences de l'existence d'un algorithme fortement polynomial pour la programmation linéaire?

L'un des Saint Graal de la conception d'algorithmes est de trouver un algorithme fortement polynomial pour la programmation linéaire, c'est-à-dire un algorithme dont l'exécution est délimitée par un polynôme dans le nombre de variables et de contraintes et est indépendante de la taille de la représentation des paramètres (en supposant arithmétique des coûts unitaires). La résolution de cette question aurait-elle des implications en dehors de meilleurs algorithmes de programmation linéaire? Par exemple, l'existence / la non-existence d'un tel algorithme aurait-elle des conséquences sur la géométrie ou la théorie de la complexité?

Edit: Je devrais peut - être clarifier ce que j'entends par conséquences. Je recherche des conséquences mathématiques ou des résultats conditionnels, des implications qui sont connues pour être vraies maintenant . Par exemple: "un algorithme polynomial pour LP dans le modèle BSS séparerait / réduirait les classes de complexité algébrique FOO et BAR", ou "s'il n'y a pas d'algorithme fortement polynomial alors il résout telle ou telle conjecture sur les polytopes", ou "un un algorithme fortement polynomial pour le problème X qui peut être formulé comme un LP aurait des conséquences intéressantes blah ". La conjecture de Hirsch serait un bon exemple, sauf qu'elle ne s'applique que si le simplexe est polynomial.

Cela montrerait que les jeux de parité et de gain moyen sont en P. Voir Sven Schewe. Des jeux de parité et de gains à la programmation linéaire. MFCS 2009.

Cela dépend de la réponse. Si l'algorithme créé a un temps d'exécution , alors cela aurait très peu d'impact. D'un autre côté, si cela conduit à une nouvelle façon de résoudre les LPs, cela pourrait avoir un impact énorme. Par exemple, si je me souviens bien de l'histoire (et je me trompe peut-être complètement ), l'algorithme ellipsoïde, par exemple, en plus de sa signification théorique, a conduit (?) Au développement de la méthode du point intérieur, qui était plus rapide dans certains cas que le simplexe algorithme. Cela a conduit à une accélération significative dans la pratique, car les deux approches ont été pressées pour la limite maximale de ce qui peut être fait.$(d n)^{Ackerman(10000)}$

Voici une conséquence pour la géométrie: Une borne fortement polynomiale pour toute variante (aléatoire ou déterministe) de l'algorithme simplex implique une borne polynomiale sur le diamètre de n'importe quel graphe polytopique. Cela implique que la "version polynomiale" de la conjecture de Hirsch est vraie.