Dlaczego problemy związane z NP są tak różne pod względem ich przybliżenia?

Chciałbym rozpocząć pytanie od stwierdzenia, że ​​jestem programistą i nie mam dużego doświadczenia w teorii złożoności.

Jedną z rzeczy, które zauważyłem, jest to, że o ile wiele problemów jest NP-zupełnych, o tyle w przypadku problemów z optymalizacją niektóre są znacznie trudniejsze do oszacowania niż inne.

Dobrym przykładem jest TSP. Chociaż wszystkie rodzaje TSP są kompletne z NP, odpowiednie problemy z optymalizacją stają się łatwiejsze i łatwiejsze do przybliżenia dzięki kolejnym uproszczeniom. Ogólny przypadek jest kompletny z NPO, metryczny jest kompletny z APX, a przypadek euklidesowy faktycznie ma PTAS.

Wydaje mi się to sprzeczne z intuicją i zastanawiam się, czy jest ku temu powód.

Jednym z powodów, dla których widzimy różne złożoności aproksymacji dla problemów NP-zupełnych jest to, że warunki konieczne dla NP-zupełnego stanowią bardzo gruboziarnistą miarę złożoności problemu. Być może znasz podstawową definicję problemu będącego NP-zupełnym:$\Pi$

1. $\Pi$ jest w NP, i
2. Dla każdego innego problemu w NP, możemy przekształcić instancję z w instancję z w czasie wielomianowym, tak że jest tak-instancją , i tylko wtedy, gdy jest tak-instancją .$\Xi$$x$$\Xi$$y$$\Pi$$y$$\Pi$$x$$\Xi$

Rozważmy warunek 2: wszystko, co jest wymagane, to wziąć i zamienić go w który zachowuje odpowiedź „jednobitową” tak / nie. Nie ma żadnych warunków dotyczących na przykład względnej wielkości świadków twierdzących na tak lub nie (to znaczy wielkości rozwiązania w kontekście optymalizacji). Tak więc jedyną zastosowaną miarą jest całkowity rozmiar danych wejściowych, który daje bardzo słaby warunek co do wielkości rozwiązania. Więc przekształcenie w jest dość „łatwe” .$x$$y$$\Xi$$\Pi$

Widzimy różnicę w różnych problemach z kompletnym NP, patrząc na złożoność niektórych prostych algorytmów. -Kolorowanie ma brutalną siłę (gdzie jest rozmiarem wejściowym). Dla -Dominating Set, podejście brutalnej siły przyjmuje . Są to w istocie najlepsze dokładne algorytmy, jakie mamy. -Vertex Cover ma jednak bardzo prosty algorytm (wybierz krawędź, gałąź, na której ma się znaleźć punkt końcowy, zaznacz wszystkie zakryte, idź dalej, dopóki nie zaznaczysz żadnych krawędzi lub nie uderzysz twój budżet$k$$O(k^{n})$$n$$k$$O(n^{k})$$k$$O(2^{k}n^{c})$$k$i Bactrack). W przypadku wielomianowych redukcji wielokrotnych jeden raz (redukcji Karp, tj. Tego, co robimy w warunku 2 powyżej), problemy te są równoważne.

Kiedy zaczynamy zbliżać się do złożoności za pomocą nawet nieco bardziej delikatnych narzędzi (złożoność aproksymacji, złożoność sparametryzowana, wszelkie inne, o których nie mogę myśleć), stosowane przez nas redukcje stają się bardziej rygorystyczne, a raczej bardziej wrażliwe na strukturę rozwiązania, oraz różnice zaczynają się pojawiać; -Vertex Cover (jak wspomniano Yuval) ma proste przybliżenie 2 (ale nie ma FPTAS, chyba że niektóre klasy złożoności się zawalą), -Dominating Set ma algorytm aproksymacji (ale nie - aproksymacja dla niektórych ), a aproksymacja wcale nie ma sensu w przypadku prostej wersji Coloring.$k$$k$$(1+\log n)$$(c\log n)$$c>0$$k$

Jednym ze sposobów rozważenia różnicy między wersją decyzyjną a wersją optymalizacyjną jest rozważenie różnych wersji optymalizacyjnych tej samej wersji decyzyjnej. Weźmy na przykład problem MAX-CLIQUE, który jest bardzo trudny do oszacowania pod względem zwykłego parametru - wielkości kliki. Jeśli zmienimy parametr optymalizacji na logarytm wielkości kliki, otrzymamy problem z algorytmem aproksymacji . W przypadku zmiany parametrów optymalizacji do 1 / 2 + k / n , gdzie K jest rozmiarem klika, możemy uzyskać O ( 1 $O(\log n)$$1/2 + k/n$$k$$O(1)$ algorytm aproksymacyjny.

Te przykłady nie są w pełni wymyślone. Problemy zestawu MAX-INDEPENDENT-SET (odpowiednik MAX-CLIQUE) i MIN-VERTEX-COVER są ściśle powiązane - uzupełnieniem niezależnego zestawu jest pokrywa wierzchołków. Ale chociaż ten pierwszy jest trudny do przybliżenia, drugi ma proste 2-przybliżenie.

Redukcje pokazujące twardość NP danego problemu mogą czasami być użyte do pokazania twardości aproksymacji, ale nie zawsze tak jest - zależy to od redukcji. Na przykład redukcja z MAX-INDEPENDENT-SET do MIN-VERTEX-COVER nie implikuje twardości przybliżenia tego drugiego problemu, który jest znacznie łatwiejszy do przybliżenia niż ten pierwszy.

Podsumowując, twardość NP jest tylko jednym aspektem problemu. Twardość aproksymacji jest innym aspektem i silnie zależy od pojęcia aproksymacji.

Jako intuicyjne podejście należy wziąć pod uwagę, że tworzenie wystąpień problemów związanych z NP-nie zawsze jest tak trudne, jak w przypadku ogólnym. Satysfakcjonowanie binarne (SAT) jest kompletne z NP, ale znalezienie rozwiązania A v B v C v v V v v… jest proste. Algorytmy złożoności po prostu ograniczają najgorszy przypadek, a nie przypadek średni, a nawet przypadek 90% .

Najłatwiejszym sposobem zredukowania problemu NP-zupełnego do czegoś prostszego jest po prostu wykluczenie twardych części. To oszustwo, tak. Ale często pozostałe części są nadal przydatne do rozwiązywania problemów w świecie rzeczywistym. W niektórych przypadkach granica między „łatwym” a „trudnym” jest łatwa do narysowania. Jak wskazano w przypadku TSP, istnieje znaczna redukcja trudności, ponieważ ograniczasz problem wokół „normalnych” kierunków, o których można pomyśleć. W przypadku innych problemów , trudniej jest znaleźć użyteczne sposoby na segregację łatwych i trudnych części.

Aby całkowicie opuścić sferę CS i matematyki, rozważ stary samochód. Twój przyjaciel chce nim prowadzić. Jeśli musisz mu powiedzieć: „hej, samochód działa idealnie. Po prostu nie bierz go powyżej 95 km / h. Paskudne kołysanie, które zrzuci cię z drogi”, to prawdopodobnie nie jest wielka sprawa. Twój przyjaciel prawdopodobnie chciał tylko zabrać go ze sobą po mieście. Jeśli jednak musisz mu powiedzieć: „musisz wcisnąć sprzęgło w prawo, aby przejść z 1. na 2., lub silnik zgaśnie”, może być trudniejsze dla twojego przyjaciela, aby korzystać z samochodu w mieście bez niewielkiego przeszkolenia.

Podobnie, jeśli problem NP-zupełny stanie się trudny tylko w egzotycznych przypadkach, dość szybko zmniejsza złożoność, gdy patrzysz na subdomeny. Jednakże, jeśli staje się trudny w często występujących przypadkach, nie ma tak wielu przydatnych subdomen, które unikają trudnej części.