Konsequenzen der Existenz eines stark polynomialen Algorithmus für die lineare Programmierung?

Eine der heiligen Seiten des Algorithmusdesigns ist das Auffinden eines stark polynomialen Algorithmus für die lineare Programmierung, dh eines Algorithmus, dessen Laufzeit durch ein Polynom in der Anzahl der Variablen und Nebenbedingungen begrenzt ist und von der Größe der Darstellung der Parameter unabhängig ist (vorausgesetzt, Stückkostenarithmetik). Hätte die Lösung dieser Frage Auswirkungen außerhalb besserer Algorithmen für die lineare Programmierung? Würde beispielsweise die Existenz / Nichtexistenz eines solchen Algorithmus Konsequenzen für die Geometrie oder Komplexitätstheorie haben?

Edit: Vielleicht sollte ich klären, was ich mit Konsequenzen meine. Ich suche nach mathematischen Konsequenzen oder bedingten Ergebnissen, Implikationen, von denen bekannt ist, dass sie jetzt wahr sind . Zum Beispiel: "Ein Polynomalgorithmus für LP im BSS-Modell würde die algebraischen Komplexitätsklassen FOO und BAR trennen / kollabieren" oder "Wenn es keinen stark polynomalen Algorithmus gibt, löst er die eine oder andere Vermutung über Polytope auf" oder "a stark Polynom - Algorithmus für Problem X , die als LP formuliert werden können , wäre interessant Folge haben , blah “. Die Hirsch-Vermutung wäre ein gutes Beispiel, außer dass sie nur gilt, wenn Simplex ein Polynom ist.

ds.algorithms conditional-results linear-programming computing-over-reals simplex Ian
quelle

Es versteht sich auch von selbst, dass die verwendete Proof-Technik, um dieses Ergebnis zu zeigen, in Bezug auf die Langzeitwirkung noch interessanter sein könnte als das Ergebnis.

Suresh Venkat

Antworten:

Dies würde zeigen, dass Paritäts- und Mean-Pay-off-Spiele in P sind. Siehe Sven Schewe. Von Paritäts- und Auszahlungsspielen zu linearer Programmierung. MFCS 2009.

Rahul Savani
quelle

Ausgezeichnet. Ich wünschte, ich könnte dies mehr als eine +1 geben. Das ist ein sehr cooles Ergebnis.

Suresh Venkat

Könnte jemand erläutern, wie ein stark polynomischer Algorithmus für LP dies implizieren würde? Schewe erstellt eine polynomgroße LP-Instanz mit doppelt exponentiell großen Zahlen. Fein. Nun führen wir den stark polynomialen Zeitalgorithmus darauf aus. Aber müssen wir nicht die arithmetischen Operationen simulieren, die dieser Algorithmus ausführt? Wie wird diese Simulation durchgeführt, ohne überpolynomielle Zeit aufzuwenden? (Erinnern Sie sich, dass die Zahlen doppelt exponentiell sind; ich denke, man könnte den chinesischen Resttrick machen, aber können wir Zahlen auf diese Weise in Polynomzeit vergleichen?).

Slimton

Ich habe das Papier noch nicht sorgfältig gelesen, aber soweit ich weiß, beweisen sie nur, dass das Problem in P im Real RAM / BSS-Modell ( en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2) liegt % 80% 93Smale_machine ), nicht die normale Version von P. Sie können Berechnungsmodelle für jeden Ring R definieren (siehe ams.org/notices/200409/fea-blum.pdf ). Über

wir normale Turingmaschinen und über den Real

wir das BSS-Modell. Jeder Ring hat eine eigene Version von P, die möglicherweise nicht der Standardversion von P entspricht.

Z_{2}

$\mathbb{Z}_2$

R

$\mathbb{R}$

Ian

Erläuterung zu meinem vorherigen Kommentar: Wenn es für LP einen stark polynomialen Algorithmus gibt, dann ist er im BSS-Modell polynomisch. In diesem Fall impliziert die Arbeit, dass Paritäts- und Auszahlungsspiele auch im BSS-Modell in P sind.

Ian

@ Ian: Mit anderen Worten: Diese Antwort war etwas irreführend (aber das hat Sie nicht davon abgehalten, sie als gültige Antwort zu akzeptieren).

Slimton

$(d n)^{Ackerman(10000)}$ ) Der Ellipsoidalgorithmus zum Beispiel führte neben seiner theoretischen Bedeutung (?) zur Entwicklung der Innenpunktmethode, die in einigen Fällen schneller war als der Simplexalgorithmus. Dies führte in der Praxis zu einer deutlichen Beschleunigung, da beide Ansätze auf die maximale Grenze der möglichen Maßnahmen beschränkt waren.

Sariel Har-Peled
quelle

Diese Bedingungen gelten jedoch für so ziemlich jedes theoretische Ergebnis: Je nach Laufzeit kann es nützlich sein oder auch nicht, und die Techniken / Ideen im Ergebnis können zu zukünftigen Fortschritten führen.

Ian

Nicht wirklich. Wenn irgendeine Form der Hirsch-Vermutung wahr ist und der Beweis konstruktiv ist, würde dies mit ziemlicher Sicherheit zu schnelleren Lösern für LP führen. Kurz gesagt, wenn die Frage spezifisch ist, sind ihre Implikationen klar, und wenn die Frage weit gefasst ist, kann sie zu nichts führen. Oder anders, die einzige sichere Folge Polynomialzeitalgorithmus für LP setzen ist , dass wir das Problem besser verstehen würde , als wir jetzt tun.

Sariel Har-Peled

Hier ist eine Konsequenz für die Geometrie: Ein starkes Polynom, das für eine beliebige (randomisierte oder deterministische) Variante des Simplex-Algorithmus gebunden ist, impliziert ein Polynom, das für den Durchmesser eines beliebigen Polytopgraphen gebunden ist. Dies impliziert, dass die "Polynomversion" der Hirsch-Vermutung wahr ist.

Shiva Kintali
quelle

Es gibt jedoch keinen Grund zu der Annahme, dass ein stark polynomialer Zeitalgorithmus für LPs die Simplex-Methode verwenden muss. Die bisher bekanntesten Methoden (subexponentiell) verwenden eine zufällige Samping + Rekursionsstrategie.

Suresh Venkat

Hoppla. Ich habe den Punkt verpasst.

Shiva Kintali

Dies gilt nur, wenn Simplex stark polynomisch ist. Ich suche nach Ergebnissen, die allgemeiner gelten. Es könnte sein, dass die polynomische Hirsch-Vermutung falsch ist, aber ein anderer Algorithmus stark polynomisch ist, oder dass die polynomische Hirsch-Vermutung wahr ist, aber Simplex exponentiell ist, weil es in der Polynomzeit keinen kurzen Weg findet.

Ian,

@Suresh: Eigentlich bin ich ziemlich sicher , dass die subexponentiellen Stichprobe + Rekursion Strategie , die Sie erwähnen (? Clarkson-Matoušek-Sharir-Welzl / Kalai, rechts) ist ein Dual - Simplex - Algorithmus. (Dies widerspricht jedoch nicht Ihrem Standpunkt.)

Jeffs

Oh, Moment mal. Hat Michael Goldwasser das nicht schon vor langer Zeit in einem SIGACT-Artikel geklärt? Hmm. jetzt muss ich gehen und graben.

Suresh Venkat