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

27

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?

cc.complexity-theory co.combinatorics optimization

— alekdimi
źródło

14

Z pewnością jest ich wielu. Dwustronne i ogólne dopasowanie oraz cięcia minimalne są trzema klasycznymi rozwiązanymi dyskretnymi problemami wielomianowymi. Wiele problemów związanych z ciągłą niewypukłą optymalizacją jest trudnych dla NP: znalezienie średnicy zestawu wypukłego lub obliczenie normy iniekcyjnej tensora 3-d.

— Sasho Nikolov,

6

Oto prosty problem ciągłej optymalizacji, który trudno jest rozwiązać NP: cstheory.stackexchange.com/questions/14630/…

— Jukka Suomela

8

Nie jestem pewien, jakie problemy masz na myśli, ale wiele ciągłych problemów, które są „rozwiązywane” za pomocą metod gradientowych, nie są tak naprawdę „rozwiązywane”: metoda po prostu znajduje jakieś lokalne optimum.

— Suresh Venkat

1

Wszystkie dotychczasowe odpowiedzi wydają się kontrprzykładami, ale fajnie byłoby zobaczyć przypadki, w których ta reguła wydaje się być prawdziwa. Dwa, które przychodzą na myśl, to programowanie liniowe vs programowanie liczb całkowitych i optymalizacja wypukła vs maksymalizacja submodularna.

— usul

13

Myślę, że cała sprawa dyskretna kontra ciągła to czerwony śledź. Problem musi mieć bardzo specjalną strukturę, aby można go było skutecznie rozwiązać. Myślę, że prawdziwa różnica polega na tym, że w przypadku łatwych ciągłych problemów specjalna struktura ma tendencję do wypukłości, podczas gdy w przypadku łatwych dyskretnych problemów sprawy wyglądają na bardziej skomplikowane: czasami struktura jest subodularna lub przecięcie matroidu, ale często tak nie jest. Prawdopodobnie ma to więcej wspólnego z faktem, że nie rozumiemy jeszcze dobrze dyskretnej matematyki.

— Sasho Nikolov

41

Przykładem, który uwielbiam, jest problem, w którym, biorąc pod uwagę różne , decydujesz, czy: $a_1, a_2, \ldots, a_n \in \mathbb{N}$

\int_{- π}^{π} \cos (a_{1} z) \cos (a_{2} z) \dots \cos (a_{n} z) d z \neq 0

$\int_{-\pi}^{\pi} \cos(a_1 z) \cos(a_2 z) \ldots \cos(a_n z) \, dz \ne 0$

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$

— Joe Bebel
źródło

4

Ponieważ zajmujemy się tym tematem, najwcześniejsze odniesienie do tego problemu, jakie mogę znaleźć, znajduje się w „The Nature of Computation” autorstwa Moore'a i Mertensa. Nie zawierają żadnych odniesień, więc zakładam, że albo je wymyślili, albo pochodzą z folkloru. Byłbym wdzięczny, gdyby ktoś znał źródło tego problemu.

— Joe Bebel,

Przypuszczalnie nie tylko większość, ale wszystkie techniki numeryczne skalują się katastrofalnie na wystarczająco duże ? Ponieważ problem jest NP-zupełny, dokładna technika numeryczna do oceny tej całki skalowanej wielomianowo w wystarczyłaby, aby pokazać P = NP.

n

$n$

n

$n$

— PE

1

Prawo, algorytm, który zawsze ocenia integralnego poprawnie w czasie w wielomian będzie wystarczające dla wykazania, P = NP. Z drugiej strony, nie mogę w 100% wykluczyć możliwości pewnych technik numerycznych, których nie jestem świadomy, jakoś dobrze sobie radzą w określonych przypadkach tej całki, nawet gdy jest duże, podobnie jak często solwery SAT znaleźć zadowalające przypisania dla niektórych formuł z tysiącami zmiennych, nawet jeśli najgorsza wydajność jest zła. Więc nawet jeśli wątpię w istnienie takich metod, trochę zabezpieczyłem swoją odpowiedź.

n

$n$

n

$n$

— Joe Bebel,

3

Najwyraźniej pierwotnym źródłem tego problemu jest: David Plaisted, Niektóre problemy podzielności wielomianowej i całkowitej są trudne NP. SIAM Journal on Computing, 7 (4): 458–464, 1978. Odniesienie znajduje się z tyłu Moore'a i Mertensa, po prostu nie w samym tekście.

— Joe Bebel,

26

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).

— David Eppstein
źródło

1

„Najkrótsza ścieżka między wielościennymi przeszkodami” jest ciągła tylko z nazwy, prawda? Możemy myśleć o przestrzeni konfiguracyjnej jako połączeniu szeregu dyskretnych elementów odpowiadających ścieżkom, które „ściskają” dany zestaw przeszkód; wtedy lokalna optymalizacja w obrębie każdego elementu (tj. w obrębie dowolnego zestawu przeszkód) jest prosta, ale decydowanie o tym, która ze ścieżek ma najlepszy na świecie dystans, jest trudną częścią problemu.

— Steven Stadnicki

13

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ć $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.

— Steven Stadnicki
źródło

4

Bardzo podoba mi się ten przykład, choć warto podkreślić, że istnieją poważne powody, by sądzić, że nie jest on NP-zupełny; patrz ( cstheory.stackexchange.com/a/4010/8985 )

— Joe Bebel

@JoeBebel Bardzo dobra uwaga - nieznacznie poprawiłem swój język, aby to odzwierciedlić. Dziękuję Ci!

— Steven Stadnicki

6

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.

— Mehrdad
źródło

Myślę, że dyskrecja jest również częścią problemu. Powiedzmy na przykład, że masz wariant LP ILP. Możesz na przykład dążyć do znalezienia rozwiązania dla wariantu LP, ale nadal są 2^n„ interesujący sąsiedzi ”, których musisz szukać.

— Willem Van Onsem,

@CommuSoft: Nie bardzo ... dyskretność nie jest problemem. Sprawdź problem najkrótszej ścieżki , który jest problemem dyskretnym, ale mimo to sprowadza się do specjalnego przypadku zintegrowanego programowania liniowego , który można rozwiązać w czasie P (nie mylić z całkowitym programowaniem liniowym , które jest oczywiście trudne NP).

— Mehrdad

nie jest to naprawdę niespodzianką: ponieważ programowanie liniowe liczb całkowitych jest zakończone NP, każdy problem w P (który można rozwiązać w czasie wielorakim), może zostać przekształcony w czasie wielorakim w problem ILP.

— Willem Van Onsem,

@CommuSoft: Czy w pełni przeczytałeś komentarz? Nie mówię o ILP.

— Mehrdad

przepraszam, czytaj szybko. Ale nadal dzieje się tak, ponieważ ograniczenia są całkowicie niemodularne , więc tylko dzięki „łasce” dobrze skonstruowanych ograniczeń takie problemy można łatwo rozwiązać. Ogólnie dyskretyzacja stanowi problematyczny aspekt problemów.

— Willem Van Onsem,

5

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}$

\frac{{\vec{x}}^{T} \cdot Q \cdot \vec{x}}{2} + {\vec{c}}^{T} \cdot \vec{x}

$\dfrac{\vec{x}^T\cdot Q\cdot\vec{x}}{2}+\vec{c}^T\cdot\vec{x}$

A \cdot \vec{x} \leq \vec{b}

$A\cdot\vec{x}\leq\vec{b}$

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

— Willem Van Onsem
źródło

2

Akapit z definicjami jest rzeczywiście niejasny. Knapsack to problem optymalizacji NP. Nie jest prawdą, że „nie wiadomo”, jeśli wersja optymalizacyjna jest w NP: nie jest tak, z definicji. Nie sądzę też, abyśmy znali jakikolwiek problem, który jest NP-zupełny pod warunkiem, że NP nie jest równy PIe 3-SAT będzie NP-zupełny, nawet jeśli P = NP (faktycznie jeśli P = NP każdy problem w P jest NP kompletny).

— Sasho Nikolov

@ AndrásSalamon: punkt zajęty. Usunąłem tę część. To było naprawdę trochę niechlujne.

— Willem Van Onsem,

@ AndrásSalamon: najwyraźniej to prawda. Dlatego mówi: „ Biorąc pod uwagę, że P nie jest równe NP, problemy te nie mogą być NP-zupełne. ”

— Willem Van Onsem,

@ AndrásSalamon: Cóż, jeśli P=NPkażdy problem w NP-complete jest z definicji częścią NP, a zatem rozszerzeniem P , teraz P oznacza, że istnieje algorytm wielomianowy. Chodzi o to, że myślę, że transformacja nie ma znaczenia, ponieważ dla każdego języka w P musi istnieć algorytm wielomianowy. Nieważne, czy zastosujesz transformację (co najwyżej wielomianową), czy nie. Pozostaje wielomianu, zatem P . Innymi słowy, ponieważ oryginalny element znajduje się w P , każdą transformację wieloczasową można wziąć za darmo (nie powodując wyższej klasy złożoności).

— Willem Van Onsem,

2

Plecak jako problem optymalizacji na pewno nie jest NP-kompletny, ponieważ nie jest to problem decyzyjny, więc nie w NP. W każdym razie rozumiem, co mówisz, ale jest to rodzaj szczegółów na poziomie licencjackim, które moim zdaniem powinny być brane za pewnik na forum badawczym, takim jak CStheory @ SE, tak jak nie oczekuję wyjaśnienia o tym, jak zbieżność prawdopodobieństwa nie jest tym samym, co prawie pewna zbieżność na Mathoverflow.

— Sasho Nikolov