Lista problemów NP-zupełnych - List of NP-complete problems

Jest to lista niektórych z bardziej znanych problemów, które są NP-zupełne, gdy są wyrażone jako problemy decyzyjne . Ponieważ znane są setki takich problemów, lista ta nie jest w żaden sposób wyczerpująca. Wiele problemów tego typu można znaleźć w Garey & Johnson (1979) .

Wykresy i hipergrafy

Wykresy występują często w codziennych zastosowaniach. Przykładami są sieci biologiczne lub społecznościowe, które w niektórych przypadkach zawierają setki, tysiące, a nawet miliardy węzłów (np. Facebook czy LinkedIn ).

1-planarność
Dopasowanie trójwymiarowe
Wymiar dwustronny
Pojemnościowe minimalne drzewo opinające
Problem kontroli trasy (zwany także problemem chińskiego listonosza ) dla grafów mieszanych (mających zarówno krawędzie skierowane, jak i nieskierowane). Program można rozwiązać w czasie wielomianowym, jeśli graf ma wszystkie krawędzie nieskierowane lub wszystkie skierowane. Warianty obejmują problem wiejskiego listonosza.
Problem kliki
Kompletna kolorystyka , aka liczba achromatyczna
Numer domatyczny
Dominujący zestaw , aka liczba dominacji

Przypadki specjalne NP-zupełne obejmują problem zbiorów dominujących brzegowych , tj. problem zbiorów dominujących w grafach liniowych. Warianty NP-zupełne obejmują problem połączonego zbioru dominującego i problem maksymalnego drzewa opinającego liście .

Problem z przepustowością
Problem z okładką kliki
Kolorowanie rangi, czyli rangi cyklu
Drzewo opinające ograniczone stopniami
Dokładny problem z okładką . Pozostaje NP-kompletny na 3 serie. Do rozwiązania w czasie wielomianowym dla 2 zestawów (jest to dopasowanie ).
Zestaw wierzchołków opinii
Zestaw sprzężenia zwrotnego
Wykres problemu homomorfizmu
Kolorowanie wykresu
Wykres partycji w subgraphs poszczególnych rodzajów (trójkąty izomorficznych subgraphs , Hamiltona subgraphs, lasy , wybór skojarzeń ) są znane NP-zupełny. Podziałowi klik ten sam problem jak farbowanie do uzupełnienia danego wykresu. Powiązanym problemem jest znalezienie przegrody, która jest optymalnym pod względem liczby krawędzi między częściami.
Uzupełnienie hamiltonowskie
Problem ścieżki hamiltonowskiej , skierowanej i nieskierowanej.
Problem z najdłuższą ścieżką
Podwykres maksymalny dwudzielny lub (zwłaszcza w przypadku ważonych krawędzi) maksymalne cięcie .
Maksymalny niezależny zestaw
Maksymalna indukowana ścieżka
Numer przecięcia wykresu
Wymiar metryczny wykresu
Minimalny k-cut
Drzewo Steinera lub Minimalne drzewo opinające dla podzbioru wierzchołków grafu. (Minimalne drzewo opinające dla całego grafu można rozwiązać w czasie wielomianowym).
Maksymalizacja modułowości
Szerokość ścieżki
Set cover (zwany także problemem minimalnego pokrycia ) Jest to równoważne, transponując macierz incydentów, do problemu trafienia zestawu.
Ustaw problem dzielenia
Drzewo opinające o najkrótszej całkowitej długości ścieżki
Testowanie skarpy numer dwa
Szerokość drzewa
Pokrywa wierzchołka

Programowanie matematyczne

Problem z trzema partycjami
Problem z pakowaniem do kosza
Problem plecakowy , kwadratowy problem plecakowy i kilka wariantów
Wariacje na temat problemu komiwojażera . Problem dla grafów jest NP-zupełny, jeśli długości krawędzi przyjmuje się jako liczby całkowite. Problem dla punktów na płaszczyźnie jest NP-zupełny z dyskretną metryką euklidesową i metryką prostoliniową. Wiadomo, że problem jest NP-trudny z (niedyskretyzowaną) metryką euklidesową.
Sprzedawca podróżujący wąskim gardłem
Programowanie liczb całkowitych . Wariant, w którym zmienne muszą mieć wartość 0 lub 1, zwany programowaniem liniowym zero-jedynkowym, a kilka innych wariantów jest również NP-zupełnych
Kwadraty łacińskie (Problem określenia, czy częściowo wypełniony kwadrat można uzupełnić w jeden)
Numeryczne dopasowanie trójwymiarowe
Problem z partycją
Kwadratowy problem przypisania
Rozwiązywanie wielomianów kwadratowych z dwiema zmiennymi po liczbach całkowitych. Biorąc pod uwagę dodatnie liczby całkowite , znajdź dodatnie liczby całkowite takie, że ${\ Displaystyle \ textstyle A, B, C \ geq 0}$ $x,y$ ${\ Displaystyle Ax ^ {2} + By-C = 0}$
Programowanie kwadratowe (NP-trudne w niektórych przypadkach, P jeśli wypukłe)
Problem sum podzbiorów

Języki formalne i przetwarzanie ciągów

Najbliższy ciąg
Najdłuższy wspólny problem z podciągami w wielu ciągach
Ograniczony wariant problemu korespondencji pocztowej
Najkrótsza wspólna supersekwencja
Problem z korekcją ciąg-do-ciągu

Gry i łamigłówki

Torba (Corral)
Okręt wojenny
Bulls and Cows , sprzedawany jako Master Mind : pewne problemy z optymalizacją, ale nie sama gra.
Wieczność II
( Uogólnione ) FreeCell
Fillomino
Hashiwokakero
Heyawake
( Uogólnione ) Natychmiastowe Szaleństwo
Kakuro (Krzyżowe sumy)
Królestwoino
Kuromasu (znany również jako Kurodoko)
Zbiornik laserowy
Lemingi (z wielomianowym limitem czasu)
Zapalić
Masyu
Problem spójności Sapera (ale zobacz Scott, Stege i van Rooij)
Nimber (lub liczba Grundy'ego) grafu skierowanego.
Numerlink
Nonogramy
Nurikabe
( Uogólnione ) Pandemia
Optymalne rozwiązanie dla kostki Rubika $N \times N \times N$
Ta sama gra
( Uogólnione ) Ustaw
Slither Link na różnych siatkach
( Uogólnione ) Sudoku
Pokaż tentai
Problemy związane z Tetris
Arytmetyka werbalna

Inne

Problem z alokacją nabrzeża
Pomiędzy
Montaż optymalnego bloku Bitcoin .
Problem spełnialności logicznej (SAT). Istnieje wiele odmian, które są również NP-zupełne. Ważnym wariantem jest sytuacja, w której każda klauzula ma dokładnie trzy literały (3SAT), ponieważ jest używana w dowodzie wielu innych wyników NP-zupełności.
Spójne zapytanie logiczne
Zamawianie cykliczne
Problem spełnialności obwodu
Problem z lokalizacją obiektu nieobsługiwanego
Problem z planowaniem sklepu Flow Shop
Uogólniony problem przypisania
Testowanie płaskości w górę
Znalezienie globalnego minimalnego rozwiązania problemu Hartree-Fock
Problem szpitali i rezydentów z parami
Niektóre problemy związane z planowaniem warsztatów
Trójkąt monochromatyczny
Minimalna maksymalna niezależna seria, czyli minimalna niezależna dominująca seria

Przypadki specjalne NP-zupełne obejmują problem minimalnego maksymalnego dopasowania , który jest zasadniczo równy problemowi zbiorów dominujących na krawędziach (patrz wyżej).

Problem izomorfizmu maksymalnego wspólnego podgrafu
Minimalny stopień drzewa opinającego
Minimalne drzewo opinające k
Centrum k metryczne
Maksymalna 2-satysfakcja
Logika modalna S5-Spełnialność
Niektóre problemy związane z planowaniem wieloprocesorowym
Podmacierz maksymalnej objętości – Problem z wyborem najlepiej uwarunkowanego podzbioru większej macierzy. Ta klasa problemów jest związana z rangą ujawniającą faktoryzację QR i D optymalnym projektem eksperymentalnym. $m\razy n$
Minimalne łańcuchy addycyjne dla sekwencji. Złożoność minimalnych łańcuchów dodawania dla poszczególnych liczb jest nieznana.
Nieliniowe wielomiany jednowymiarowe nad GF[2 ⁿ ], n długością wejścia. Rzeczywiście, nad dowolnym GF[q ⁿ ].
Planowanie otwartego sklepu
Szerokość ścieżki lub, równoważnie, grubość odstępu i numer separacji wierzchołków
Problem z odległością sortowania naleśników dla ciągów
k-chiński listonosz
Problem izomorfizmu podgrafów
Wariacje problemu drzewa Steinera . W szczególności z dyskretną metryką euklidesową, metryką prostoliniową. Wiadomo, że problem jest NP-trudny z (niedyskretyzowaną) metryką euklidesową.
Zestaw do pakowania
Serializacja historii baz danych
Planowanie w celu zminimalizowania ważonego czasu realizacji
Rzadkie przybliżenie
Sortowanie bloków (sortowanie według ruchów bloków)
Instancja drugiego rzędu
Szerokość drzewa
Testowanie, czy drzewo może być reprezentowane jako minimalne euklidesowe drzewo opinające
Trójwymiarowy model Ising
Problem z wyznaczaniem trasy pojazdu

Zobacz też

Uwagi

Bibliografia

Ogólny

Garey, Michael R .; Johnson, David S. (1979) Komputery i krnąbrność: Przewodnik do teorii Problem NP-zupełny , W. H. Freeman , ISBN 0-7167-1045-5. Ta książka to klasyka, rozwijająca teorię, a następnie katalogująca wiele problemów NP-Complete.
Cook, SA (1971). „Złożoność procedur dowodzenia twierdzeń”. Materiały, Trzecie doroczne sympozjum ACM na temat teorii obliczeń, ACM, Nowy Jork . s. 151–158. doi : 10.1145/800157.805047 .
Karp, Richard M. (1972). „Sprowadzalność wśród problemów kombinatorycznych”. W Miller, Raymond E.; Thatcher, James W. (red.). Złożoność obliczeń komputerowych . Plenum. s. 85–103.
Dunne, PE "Annotowana lista wybranych problemów NP-zupełnych" . COMP202, Wydział Informatyki, Uniwersytet w Liverpoolu . Źródło 21 czerwca 2008 .
Crescenzi, P.; Kann, V.; Halldorsson, M.; Karpiński, M. ; Woeginger, G . "Kompendium problemów optymalizacji NP" . KTH NADA, Sztokholm . Źródło 21 czerwca 2008 .
Dahlke, K. "Problemy NP-zupełne" . Matematyczny projekt referencyjny . Źródło 21 czerwca 2008 .

Specyficzne problemy

Friedman, E (2002). "Puzzle perłowe są NP-kompletne" . Uniwersytet Stetson, DeLand, Floryda . Źródło 21 czerwca 2008 .
Grigoriew, A; Bodlaender, HL (2007). „Algorytmy dla wykresów osadzanych z kilkoma przejściami na krawędź”. Algorytmika . 49 (1): 1–11. CiteSeerX 10.1.1.61.3576 . doi : 10.1007/s00453-007-0010-x . MR 2344391 . S2CID 8174422 .
Hartung, S; Nichterlein, A (2012). Jak oblicza świat . Notatki z wykładów z informatyki. 7318 . Springer, Berlin, Heidelberg. s. 283–292. CiteSeerX 10.1.1.377.2077 . doi : 10.1007/978-3-642-30870-3_29 . Numer ISBN 978-3-642-30869-7. S2CID 6112925 .
Holzer, Markus; Ruepp, Oliver (2007). „Kłopoty projektowania wnętrz – analiza złożoności gry Heyawake” (PDF) . Materiały, IV Międzynarodowa Konferencja Zabawy z Algorytmami, LNCS 4475 . Springer, Berlin/Heidelberg. s. 198-212. doi : 10.1007/978-3-540-72914-3_18 . Numer ISBN 978-3-540-72913-6.
Kaye, Richard (2000). „Saper jest NP-kompletny”. Inteligencja matematyczna . 22 (2): 9-15. doi : 10.1007/BF03025367 . S2CID 122435790 .Więcej informacji można znaleźć w Internecie na stronach Sapera Richarda Kaye .
Kashiwabara, T.; Fujisawa, T. (1979). „NP-zupełność problemu znalezienia grafu przedziałów o minimalnej liczbie klik zawierającej dany graf jako podgraf”. Postępowanie . Międzynarodowe Sympozjum Obwodów i Systemów . s. 657-660.
Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). „Jednowymiarowe przypisanie bramki logicznej i wykresy interwałowe”. Transakcje IEEE w obwodach i systemach . 26 (9): 675–684. doi : 10.1109/TCS.1979.1084695 .
Lengauer, Thomas (1981). „Czarno-białe kamyki i separacja wykresów”. Acta Informatica . 16 (4): 465–475. doi : 10.1007/BF00264496 . S2CID 19415148 .
Arnborga, Stefana; Corneil, Derek G .; Proskurowski, Andrzej (1987). „Złożoność znajdowania osadzeń w k- drzewie”. SIAM Journal on Algebraic and Discrete Methods . 8 (2): 277–284. doi : 10.1137/0608024 .
Cormode, Graham (2004). „Twardość gry lemingi lub O nie, więcej dowodów NP-zupełności”. Materiały III Międzynarodowej Konferencji Zabawy Algorytmami (FUN 2004) . s. 65-76.

Languages

In other projects