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.

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 L, 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ć S na dwa mniejsze podzbiory S 1 i S 2, w których sprawdzę podobną właściwość? Humm ... niezupełnie. Może gdybym sprawdził wszystkie kombinacje S 1 i S 2, 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 C przejść przez B to nie jest dłużej niż najkrótszej ścieżki od A do B plus najkrótsza z B do C .$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.

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.