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

23

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$

max_{x} f (x) = min_{y} g (y)

$\max_x f(x) = \min_y g(y)$

x

$x$

n

$n$

y

$y$

m

$m$

n

$n$

m

$m$

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!

— Andras Farago
źródło

22

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$

— Noam
źródło

9

Miałem wrażenie, że niektórzy posunęli się nawet tak daleko, że przyjęli jako definicję „dobrej charakterystyki”.

N P \cap c o N P

$\mathsf{NP} \cap \mathsf{coNP}$

— Joshua Grochow

Lista takich problemów znajduje się na stronie mathoverflow.net/questions/31821/…

— Rahul

14

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$

Dla wszystkich , . $x \in V(T)$ $|S(x)| \leq k+1$
Sumą wszystkich jest zbiorem wierzchołek . $S(x)$ $G$
Dla każdego podgrupa indukowana przez wszystkie dla których jest podłączony. $u \in V(G)$ $T$ $x$ $u \in S(x)$
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$

Każde dwa podgrafy przecinają się lub są połączone krawędzią.
Ż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)$

— Sasho Nikolov
źródło

1

Dziękuję, to bardzo ładny przykład, nawet jeśli nie mieści się w kategorii, której szukam. Warto zauważyć, że to twierdzenie min-max o szerokości grzbietu zostało opublikowane w 1993 r., A wówczas znana była już zupełność NP szerokości grzbietu. Dlatego wynik mógł posłużyć jako powód do przypuszczenia, że NP = coNP. Chociaż wykładnicza dolna granica wielkości jeżyny ostatecznie zdyskwalifikowała ją do tej roli, ta dolna granica została opublikowana dopiero 16 lat później.

— Andras Farago

Andras, w tym czasie wiedział również, że uderzenie zestawu jest ogólnie trudne do NP (był to jeden z 21 problemów Karpa). Tak więc nawet w przypadku wielomianów o rozmiarach jeżyn obliczanie kolejności nie jest łatwe, chyba że można w jakiś sposób użyć struktury jeżyn. Ciekawe jest jednak to, że rozmiar jeżyn nie był wcześniej badany.

— Sasho Nikolov

13

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

— Rahul Savani
źródło