Ogólna zasada, aby wiedzieć, czy problem może być NP-zupełny

To pytanie zostało zainspirowane komentarzem na StackOverflow .

Oprócz znajomości problemów NP-zupełnych z książki Garey Johnson i wielu innych; czy istnieje ogólna zasada, aby wiedzieć, czy problem wygląda jak NP-zupełny?

Nie szukam czegoś rygorystycznego, ale czegoś, co działa w większości przypadków.

Oczywiście za każdym razem, gdy musimy udowodnić, że problem jest NP-zupełny lub niewielki wariant NP-zupełny; ale zanim pospieszysz do dowodu, wspaniale byłoby mieć pewność co do pozytywnego wyniku dowodu.

complexity-theory np-complete intuition

— Виталий Олегович
źródło

Moja ogólna zasada jest prosta: jeśli nie pachnie jak problem, który już znam, prawdopodobnie jest trudny do NP (lub gorzej).

— JeffE

@JeffE oczywiście znasz już sporo problemów ... nowicjusze w CS mogą nie być w stanie korzystać z tej samej reguły.

— Joe

@Joe: Prawda. Może lepiej byłoby powiedzieć: Jeśli nie dostałeś problemu z podręcznika, prawdopodobnie jest to trudne NP.

— JeffE

Innym sposobem na wyrażenie tego jest zaskakujące, gdy problem nie jest trudny do NP, niż gdy problem jest trudny do NP.

— Joe

Odpowiedzi:

To jest moje osobiste podejście do ustalenia, czy problem (tj. Język ) jest NP-zupełny, czy nie. Jeśli oba te warunki są zweryfikowane: $L$

Wydaje mi się, że sprawdzenie, czy instancja, którą w oznacza, że muszę sprawdzić wszystkie kombinacje $I$ $L$
i że nie ma sposobu na podzielenie takiej kombinacji na dwie mniejsze

wtedy może być bardzo trudne do NP. $L$

Na przykład dla problemu sumy podzbiorów muszę wymienić wszystkie podzbiory i sprawdzić, czy istnieje taki, którego suma wynosi zero. Czy mogę podzielić na dwa mniejsze podzbiory i w których sprawdzę podobną właściwość? Humm ... niezupełnie. Może gdybym sprawdził wszystkie kombinacje i ale byłoby to naprawdę długie ... $S$ $S$ $S_1$ $S_2$ $S_1$ $S_2$

Zwykle umiejętność dzielenia się na mniejsze kawałki jest dobrym wskaźnikiem problemu w P. Jest to podejście dziel i zwyciężaj . Na przykład, aby znaleźć najkrótszą drogę między dwoma punktami, można użyć tę właściwość, że jeśli najkrótsza droga od do przejść przez to nie jest dłużej niż najkrótszej ścieżki od do plus najkrótsza z do . $A$ $C$ $B$ $A$ $B$ $B$ $C$

Szczerze mówiąc, takie podejście jest bardzo podstawowe: staram się znaleźć algorytm (wielomianowy) dla danego problemu. Jeśli nie mogę go znaleźć, to z mojego punktu widzenia problem staje się „trudny”. Potem pojawia się całe rozumowanie dotyczące NP-kompletności: czy będę w stanie zakodować istniejący problem NP-complete na ten problem? (A ponieważ jest to zwykle znacznie trudniejsze, próbuję jeszcze raz znaleźć algorytm wielomianowy ..)

Podejrzewam, że jest to zwykły sposób myślenia. Jednak nadal trudno jest zastosować w przypadku nieznanych problemów. Osobiście pamiętam, jak zaskoczył mnie jeden z pierwszych przykładów kompletności NP: powiedziano mi: problem kliki . Sprawdzenie tego wydawało się takie proste! Przypuszczam, że to doświadczenie ma z tym wiele wspólnego. Również intuicja może być czasem bezużyteczna. Pamiętam, że kilkakrotnie powiedziano mi dwa prawie identyczne problemy, ale jeden był w P, a drugi z niewielką zmiennością był NP-zupełny.

Mam jeszcze dobry przykład (potrzebuję tutaj pomocy), ale jest to problem z korespondencją pocztową : jest to problem nierozstrzygalny, ale niektóre warianty są rozstrzygalne.

— jmad
źródło

+ 1

$+1$

Ciekawym wyjątkiem od reguły są problemy optymalizacji, które można rozwiązać za pomocą programowania liniowego. Jeśli nie słyszałeś o sztuczce, może być trudno zobaczyć, w jaki sposób problemy takie jak problem z przypisaniem lub dopasowanie wykresu można rozwiązać w czasie wielu, ponieważ sztuczki takie jak dzielenie i podbijanie oraz programowanie dynamiczne wydają się nie mieć zastosowania.

— hugomg

Przykładem jest najdłuższy wspólny problem podsekwencji, który występuje w P dla 2 sekwencji, ale dostaje się do NP-Hard z większą liczbą.

— Christian Vielma,

Inna perspektywa twardości problemów pochodzi od społeczności graczy i łamigłówek, gdzie ogólna zasada brzmi: „problemy są tak trudne, jak to tylko możliwe” (a wyjątki wynikają z ukrytych struktur problemu - przykład wyznacznika Massimo w komentarze są tego dobrym przykładem); sztuczka polega na zrozumieniu, jak trudny może być problem:

$n$
Zagadki obejmujące sekwencję ruchów w ograniczonej przestrzeni stanów znajdują się w PSPACE (ponieważ „drzewo ruchów” można ogólnie badać w standardowy sposób w pierwszej kolejności, wymagając jedynie miejsca na wielomianową liczbę konfiguracji), i zwykle są kompletne z PSPACE; klasycznym tego przykładem jest godzina szczytu.
Gry o wielomianowo ograniczonej głębokości są również dostępne w PSPACE; wykorzystuje to charakterystykę PSPACE jako APTIME, ponieważ zwykła charakterystyka strategii min-max doskonale naśladuje naprzemienną maszynę Turinga z jej charakterystyką: „istnieje ruch dla gracza A taki, że dla każdej odpowiedzi ruch od gracza B istnieje odpowiedź przesuń się dla gracza A tak, aby ... ”itd. Są one również pełne PSPACE; Hex i ogólne gry w kółko i krzyżyk są tego przykładem.
Gry bez ograniczonej głębokości drzewa, ale rozgrywane w (wielomianowo) ograniczonej przestrzeni, działają w WYGODZIE, ponieważ istnieje wykładniczo wiele pozycji całkowitych, a cały wykres można budować i eksplorować w czasie wielomianem pod względem liczby pozycji (a zatem ogólnej wykładniczej) ; te gry są na ogół ukończone w trybie EXPTIME. Szachy, warcaby i Go wszystkie należą do tej kategorii.

— Steven Stadnicki
źródło