Czy jest regułą, że problemy dyskretne są trudne dla NP, a problemy ciągłe nie?

W mojej edukacji informatycznej coraz częściej zauważam, że większość dyskretnych problemów jest NP-kompletna (przynajmniej), podczas gdy optymalizacja ciągłych problemów jest prawie zawsze łatwo osiągalna, zwykle za pomocą technik gradientowych. Czy są od tego wyjątki?

Przykładem, który uwielbiam, jest problem, w którym, biorąc pod uwagę różne , decydujesz, czy:∫ π - π cos ( a 1 z ) cos ( a 2 z ) … cos ( a n z $a_1, a_2, \ldots, a_n \in \mathbb{N}$

Z początku wydaje się, że jest to ciągły problem do oceny tej całki, jednak łatwo jest wykazać, że ta całka nie jest równa zero, jeśli istnieje zrównoważona partycja zestawu , więc ten problem integralny jest faktycznie NP-kompletne.$\{a_1, \ldots, a_n\}$

Oczywiście zachęcam do zabawy przy użyciu niektórych narzędzi numerycznych, aby przekonać się, że większość (jeśli nie wszystkie) sztuczki numeryczne do oceny tej całki są skazane na niepowodzenie, gdy stanie się wystarczająco duże.$n$

Istnieje wiele ciągłych problemów związanych z formą „testowanie, czy ten kombinatoryczny wkład może być zrealizowany jako struktura geometryczna”, które są kompletne dla egzystencjalnej teorii rzeczywistości , ciągłego analogu NP. W szczególności oznacza to, że problemy te są trudne NP, a nie wielomianowo możliwe do rozwiązania. Przykłady obejmują sprawdzenie, czy dany wykres jest wykresem odległości jednostkowej, czy dany wykres można narysować w płaszczyźnie z krawędziami segmentów linii prostej i co najwyżej określoną liczbą skrzyżowań, lub czy dany układ pseudoliny może zostać rozciągnięty w celu utworzenia linii układ.

Istnieją inne ciągłe problemy, które są jeszcze trudniejsze: na przykład znalezienie najkrótszej ścieżki między wielościennymi przeszkodami w 3d to PSPACE-complete (Canny i Reif, FOCS'87).

Chociaż nie odpowiada to dokładnie na twoje pierwotne pytanie, jest to (przypuszczalny) przykład pewnego rodzaju filozoficznego kontrapunktu: problem, w którym prezentacja jest dyskretna, ale cała twardość wynika z „ciągłego” aspektu problemu.

Problemem jest problem sumy kwadratowych : biorąc pod uwagę dwa zestawy liczb całkowitych i , to ? (Istnieją inne preparaty, ale jest to jeden wolę). Chociaż nie wiadomo na pewno, aby byćB = { b 1 , b 2 , … , b n } ∑ m i = 1$A=\{a_1, a_2, \ldots, a_m\}$$B=\{b_1, b_2, \ldots, b_n\}$$\sum_{i=1}^m \sqrt{a_i}\leq\sum_{j=1}^n\sqrt{b_j}$ciężko, powszechnie podejrzewa się, że może to być NP-trudne i może w rzeczywistości znajdować się poza NP (istnieją, jak zauważono w komentarzach, doskonałe powody, by sądzić, że nie jest to NP-zupełny); jedynym znanym dotychczas ograniczeniem jest kilka poziomów wyżej w hierarchii wielomianowej. Oczywiście prezentacja tego problemu jest tak dyskretna, jak to tylko możliwe - zestaw liczb całkowitych i pytanie tak / nie o nich - ale wyzwanie powstaje, ponieważ chociaż obliczanie pierwiastków kwadratowych z dowolną określoną precyzją jest łatwym problemem, może być konieczne ich obliczenie do wysokiej (potencjalnie ponad wielomianowej) dokładności w celu wyrównania nierówności w taki czy inny sposób. Jest to „dyskretny” problem, który pojawia się w zaskakującej liczbie kontekstów optymalizacji i pomaga przyczynić się do ich własnej złożoności.

Dyskretne problemy zwykle są trudniejsze (np. LP vs. ILP), ale problem nie jest sama dyskrecja ... to w jaki sposób ograniczenia wpływają na sposób przeszukiwania domeny. Na przykład możesz pomyśleć, że optymalizacja wielomianu jest czymś, co możesz zrobić efektywnie, ale decydowanie o wypukłości kwartyków (wielomiany stopnia 4) jest trudne NP .

Co oznacza, że ​​nawet jeśli już masz optymalne, po prostu udowodnienie, że jesteś optymalny, jest już trudne NP.

Chociaż w przypadku niektórych popularnych problemów jest to prawda, wydaje mi się, że oba założenia - w zależności od tego, co definiujesz jako problem optymalizacji - nie są prawdziwe.

Najpierw kilka definicji: większość problemów z optymalizacją nie jest częścią NP . Na przykład w przypadku problemu plecakowego : nie można wykorzystać niedeterminizmu do zbudowania najcenniejszej torby, proste, ponieważ różne niedeterministyczne gałęzie nie mają wspólnej pamięci. NP jest również definiowany jako „weryfikowalny wielomianowo” (weryfikacja certyfikatu) [1, p. 34]. W tym przypadku certyfikat jest na przykład torbą : ciąg bitów, w którym jeśli i -ty bit jest ustawiony, oznacza to, że i- ty element jest częścią torby. Rzeczywiście możesz sprawdzić w czasie wielomianowym, czy taka torba jest cenniejsza niż określony próg (jest to wariant decyzyjny), ale nie można - o ile wiemy - na podstawie jednej torby (wielomianowej liczby toreb) zdecydować, czy ta torba jest najcenniejsza ze wszystkich możliwych toreb. To zasadnicza różnica między na przykład NP i EXP : w EXP można wyliczyć wszystkie możliwe torby i prowadzić księgowość, która z nich jest najlepsza.

Wariant decyzja problemów optymalizacyjnych w niektórych przypadkach części NP , trzeba dokonać wyraźnego rozróżnienia między smakiem maksymalizacji i aromat decyzji . W smaku decyzyjnym pytanie brzmi: „ Biorąc pod uwagę problem optymalizacji i ograniczenie użyteczności, istnieje rozwiązanie z użytecznością większą lub równą temu ograniczeniu ” (lub nieznacznie zmodyfikowane dla problemu minimalizacji).

Zakładam również, że przez NP masz na myśli (hipotetyczny) część NP , który nie jest częścią P . Jeśli P = NP , oczywiście NP-zupełne nadal istnieje, ale będzie równe P (tylko pokrywa się z P dla niektórych pojęć redukcji, takich jak redukcje wielomianowe wielokrotne przez @ AndrásSalamon), co nie jest aż tak imponujące ( i zmniejszyłoby „ lukę ”, którą podajesz w swoim pytaniu).

Coraz bardziej zauważam, że większość dyskretnych problemów ma charakter NP.

Teraz, gdy mamy posortowane, że obecnie: istnieje wiele problemów optymalizacyjnych, które są w P : problem najkrótszej ścieżki , problem maksymalnego przepływu (dla pojemności integralnych), minimalnej Spanning Tree i maksymalnego dopasowania . Chociaż problemy te mogą wydawać się „trywialne do rozwiązania”, nadal są to problemy z optymalizacją, aw wielu przypadkach konstrukcja (i udowodnienie poprawności) nie jest taka łatwa. Więc roszczenie nie obejmuje wszystkich dyskretnych problemów, które są NP-zupełne. Biorąc pod uwagę, że P nie jest równe NP , problemy te nie mogą być NP-zupełne .

$\Sigma^P_i$

Podczas gdy optymalizacja ciągłych problemów jest prawie zawsze łatwo osiągalna.

Popularnym ciągłym problemem, który jest NP-trudny, jest programowanie kwadratowe .

$\vec{x}$

W rzeczywistości programowanie liniowe od dawna uważane jest również za trudne dla NP , ale z bardzo dobrze wykonującą heurystyką ( metoda Simplex ). Algorytm Karmarkar jest to jednak w P .

Od momentu, gdy problem optymalizacji dotyczy obiektów niewypukłych, ogólnie trudno będzie - jeśli nie niemożliwe - znaleźć skuteczny algorytm.

Bibliografia

[1] Złożoność obliczeniowa, nowoczesne podejście , Sanjeev Arora i Boaz Barak