Problemy z optymalizacją przy dobrej charakterystyce, ale bez algorytmu czasu wielomianowego

Rozważ problemy z optymalizacją w poniższym formularzu. Niech $f(x)$ będzie funkcją obliczalną w czasie wielomianowym, która odwzorowuje ciąg $x$ na liczbę wymierną. Problem optymalizacji jest następujący: jaka jest maksymalna wartość $f(x)$ ponad $n$ bitowych ciągów $x$ ?

$g$

Wiele naturalnych i ważnych problemów związanych z optymalizacją ma taką charakterystykę minimax. Kilka przykładów (twierdzenia, na których oparte są charakterystyki przedstawione w nawiasach):

Programowanie liniowe (LP Duality Thm), maksymalny przepływ (maks. Przepływ, min. Cięcie Thm), maks. Dopasowanie dwustronne (Konig-Hall Thm), maks. Dopasowanie niepodzielne na dwie strony (Thm Tutte'a, formuła Tutte-Berge), maks. Rozłączne arborescencje na ukierunkowanym wykresie ( Edmond's Disjoint Rozgałęziający Thm), Max Pakowanie Drzewa Rozpinającego w Nieukierowanym Grafice (Tutte's Tree Pakowanie Thm), Min Pokrycie przez Lasy (Nash-Williams Thm), Max Directed Cut Packing (Lucchesi-Younger Thm), Max 2-Matroid Przecięcie (Przecięcie Matroid Thm), Max Disjoint Paths (Menger's Thm), Max Antichain w zestawie częściowo zamówionym (Dilworth Thm) i wielu innych.

We wszystkich tych przykładach dostępny jest również algorytm wielomianowy w celu znalezienia optymalnego. Moje pytanie:

Czy jest jakiś problem optymalizacji z charakterystyką minimax, dla której do tej pory nie znaleziono algorytmu czasu wielomianowego?

Uwaga: Programowanie liniowe było w tym stanie przez około 30 lat!

W pewnym sensie technicznym pytasz, czy . Załóżmy, że , a więc istnieje wielozakres i tak że iff i iff . Można to przekształcić jako charakterystykę minmax o jeśli i przeciwnym razie; jeśli i przeciwnym razie. Teraz rzeczywiście mamy .$P = NP \cap coNP$$L \in NP \cap coNP$$F$$G$$x \in L$$\exists y: F(x,y)$$x \not\in L$$\exists y: G(x,y)$$f_x(y) = 1$$F(x,y)$$f_x(y) = 0$$g_x(y) = 0$$G(x,y)$$g_x(y) = 1$$max_y f_x(y) = min_y g_x(y)$

W tym sensie każdy problem, o którym wiadomo, że jest w ale nie jest znany w można przekształcić w odpowiedź na twoje pytanie. Np. Faktoring (powiedzmy, wersja decyzyjna tego, czy -ty bit największego czynnika wynosi 1).$NP \cap coNP$$P$$i$

Seymour i Thomas wykazali minimalną i maksymalną charakterystykę szerokości. Jednak szerokość drzewa jest NP-trudna. Nie jest to jednak taka charakterystyka, o którą prosisz, ponieważ funkcja podwójna nie jest funkcją obliczającą czas wielomianowy krótkiego certyfikatu. Jest to najprawdopodobniej nieuniknione w przypadku problemów NP zupełnych, ponieważ w przeciwnym razie mielibyśmy problem NP-zupełny w coNP, co oznaczałoby załamanie NP = coNP, i uważałbym to za dość szokujące.$g$

Treewidth grafu jest równa najmniejszej najmniejszej szerokości rozkładu drzewa . Rozkład drzewa na wykresie jest drzewem tak że każdy wierzchołek z jest oznaczony zestawem wierzchołków z właściwością:$G$$G$$G$$T$$x$$T$$S(x)$$G$

1. Dla wszystkich , .$x \in V(T)$$|S(x)| \leq k+1$
2. Sumą wszystkich jest zbiorem wierzchołek .$S(x)$$G$
3. Dla każdego podgrupa indukowana przez wszystkie dla których jest podłączony.$u \in V(G)$$T$$x$$u \in S(x)$
4. Każda krawędź jest podzbiorem niektórych dla .$(u, v) \in E(G)$$S(x)$$x \in V(T)$

Seymour i Thomas pokazał, że treewidth jest równa liczbie jeżyny z : maksymalna takie, że nie jest to zbiór połączonych subgraphs z tak, że:$G$$k$$G$

1. Każde dwa podgrafy przecinają się lub są połączone krawędzią.
2. Żaden zestaw wierzchołków uderza we wszystkie podgrafy.$k$$G$

Taki zbiór podgrafów nazywa się bramble rzędu$k$

Zauważ, że „liczba bramble wynosi co najmniej ” jest instrukcją , z obydwoma kwantyfikatorami w stosunku do wykładniczo dużych zbiorów. Więc nie sugeruje to łatwego do zweryfikowania certyfikatu (a jeśli byłby taki, który byłby naprawdę dużą wiadomością, jak powiedziałem powyżej). Co gorsza, Grohe i Marks wykazali, że dla każdego istnieje wykres szerokości taki, że każda pomyłka rzędu co najmniej musi składać się z wykładniczo wielu subgrafów. Pokazują również, że istnieją jezyki rzędu o wielkości wielomianowej.$k$$\exists\forall$$k$$k$$k^{1/2 + \epsilon}$$k^{1/2}/O(\log^2 k)$

Do tej kategorii należą gry parzystości, gry o średniej wypłacie, gry ze zniżką i proste gry stochastyczne.

Wszystkie z nich to nieskończone dwuosobowe gry z zerową sumą rozgrywane na wykresach, w których gracze kontrolują wierzchołki i wybierają miejsce, w którym żeton powinien być następny. Wszystkie mają równowagę w bezbłędnych strategiach pozycjonowania, co oznacza, że ​​każdy gracz wybiera krawędź przy każdym wierzchołku wyboru deterministycznie i niezależnie od historii gry. Biorąc pod uwagę strategię jednego gracza, najlepszą reakcję drugiego gracza można obliczyć w czasie wielomianowym, a wymagana relacja min-max zachowuje „wartość” gry.

Naturalne warianty decyzyjne tych problemów są w NP i co-NP (w rzeczywistości UP i co-UP), a problemy funkcji, aby znaleźć równowagę, leżą w PLS i PPAD.

Algorytmy z najbardziej znanym czasem działania są sub wykładnicze, ale super-wielomianowe (np. , gdzie jest liczbą wierzchołków na wykresie gry).$O(n^\sqrt{n})$$n$

Zobacz np.

David S. Johnson. 2007. Kolumna NP-kompletność: Znajdowanie igieł w stogach siana. ACM Trans. Algorytmy 3, 2, art. 24 (maj 2007). DOI = 10.1145 / 1240233.1240247 http://doi.acm.org/10.1145/1240233.1240247