Konsekwencje istnienia silnie wielomianowego algorytmu programowania liniowego?

Jednym ze świętych graali projektowania algorytmów jest znalezienie silnie wielomianowego algorytmu programowania liniowego, tj. Algorytmu, którego czas działania jest ograniczony wielomianem w liczbie zmiennych i ograniczeń i jest niezależny od wielkości reprezentacji parametrów (przy założeniu arytmetyka kosztów jednostkowych). Czy rozwiązanie tego pytania miałoby implikacje poza lepszymi algorytmami programowania liniowego? Na przykład, czy istnienie / nieistnienie takiego algorytmu miałoby jakiekolwiek konsekwencje dla geometrii lub teorii złożoności?

Edycja: Może powinienem wyjaśnić, co rozumiem przez konsekwencje. Szukam matematycznymi konsekwencjami lub wyników warunkowych, implikacji, które są znane, aby być prawdziwe teraz . Na przykład: „algorytm wielomianowy dla LP w modelu BSS rozdzieliłby / zwinął klasy złożoności algebraicznej FOO i BAR”, lub „jeśli nie ma algorytmu silnie wielomianowego, wówczas rozwiązuje takie i takie przypuszczenia na temat wielopianów”, lub „a mocno algorytm wielomianowy dla problemu X, który można sformułować jako LP, miałby interesujące konsekwencje bla . Hipoteza Hirscha byłaby dobrym przykładem, z tą różnicą, że ma zastosowanie tylko wtedy, gdy simplex jest wielomianem.

— Ian
źródło

oczywiste jest również, że technika dowodowa zastosowana do wykazania tego wyniku może być nawet bardziej interesująca niż wynik pod względem długoterminowego wpływu.

— Suresh Venkat

Odpowiedzi:

Oznaczałoby to, że gry o parzystości i średniej wypłacie znajdują się w P. Patrz Sven Schewe. Od gier parzystości i wypłaty po programowanie liniowe. MFCS 2009.

— Rahul Savani
źródło

doskonały. Chciałbym dać temu więcej niż jeden +1. to bardzo fajny wynik.

— Suresh Venkat

Czy ktoś mógłby wyjaśnić, w jaki sposób sugerowałby to silnie algorytm wielomianowy dla LP? Schewe tworzy wielomianową instancję LP z podwójnie wykładniczo dużymi liczbami. W porządku. Teraz uruchamiamy na nim algorytm silnie wielomianowy. Ale czy nie musimy symulować operacji arytmetycznych wykonywanych przez ten algorytm? Jak odbywa się ta symulacja bez spędzania czasu na wielomianach? (przypomnijmy, że liczby są podwójnie wykładnicze; myślę, że można zrobić sztuczkę z chińską resztą, ale czy możemy zrobić porównanie liczb w ten sposób w czasie wielomianowym?).

— slimton,

Z_{2}

$\mathbb{Z}_2$

R

$\mathbb{R}$

Wyjaśnienie do mojego poprzedniego komentarza: jeśli istnieje silnie algorytm wielomianowy dla LP, to jest on wielomianowy w modelu BSS, w którym to przypadku papier sugeruje, że gry parzystości i wypłaty są również w P w modelu BSS.

— Ian

@Ian: Innymi słowy: ta odpowiedź była nieco myląca (ale nie powstrzymało cię to od zaakceptowania jej jako prawidłowej odpowiedzi).

— slimton,

$(d n)^{Ackerman(10000)}$ ), na przykład, algorytm elipsoidalny, oprócz jego znaczenia teoretycznego, doprowadził (?) do opracowania metody punktu wewnętrznego, która w niektórych przypadkach była szybsza niż algorytm simpleksowy. Doprowadziło to do znacznego przyspieszenia w praktyce, ponieważ oba podejścia zostały ściśnięte w celu osiągnięcia maksymalnego limitu tego, co można zrobić.

— Sariel Har-Peled
źródło

Ale te warunki mają praktycznie dowolny wynik teoretyczny: może być, ale nie musi, przydatny w zależności od czasu wykonywania, a techniki / pomysły w wyniku mogą prowadzić do przyszłych postępów.

— Ian

Nie całkiem. Jeśli jakaś forma hipotezy Hirscha jest prawdziwa, a dowód jest konstruktywny, to prawie na pewno doprowadziłoby to do szybszych solverów dla LP. Krótko mówiąc, jeśli pytanie jest konkretne, to jego implikacje są jasne, a jeśli pytanie jest szerokie, może prowadzić do niczego. Innymi słowy, jedyną pewną konsekwencją algorytmu wielomianowego czasu dla LP jest to, że lepiej zrozumiemy problem niż teraz.

— Sariel Har-Peled

Oto jedna konsekwencja dla geometrii: silnie wielomianowe ograniczenie dla dowolnego wariantu (losowego lub deterministycznego) algorytmu simpleks implikuje wielomianowe ograniczenie na średnicy dowolnego wykresu wielotopowego. To implikuje, że „wielomianowa wersja” hipotezy Hirscha jest prawdziwa.

— Shiva Kintali
źródło

ale nie ma powodu, aby sądzić, że silnie wielomianowy algorytm czasu dla płyt LP musi przejść metodą simpleks. Najbardziej znane dotychczas metody (subeksponencjalne) wykorzystują losową strategię próbkowania + rekurencji.

— Suresh Venkat

Ups Nie trafiłem w sedno.

— Shiva Kintali

Dotyczy to tylko sytuacji, gdy simplex jest silnie wielomianowy. Szukam wyników, które są bardziej ogólne. Może się zdarzyć, że wielomianowa hipoteza Hirscha jest fałszywa, ale inny algorytm jest silnie wielomianowy lub że wielomianowa hipoteza Hirscha jest prawdziwa, ale simpleks jest wykładniczy, ponieważ nie może znaleźć krótkiej ścieżki w czasie wielomianowym.

— Ian

@Suresh: Właściwie jestem całkiem pewien, że wspomniana wyżej strategia subplonencjalnego losowego próbkowania + rekurencji (Clarkson-Matoušek-Sharir-Welzl / Kalai, prawda?) Jest algorytmem dual simplex. (Ale to nie jest sprzeczne z twoją

— tezą

zaczekaj. Czy Michael Goldwasser nie sprawdził tego dawno temu w artykule SIGACT? Hmm teraz muszę iść i kopać.

— Suresh Venkat