Dlaczego klasa NP-Complete jest ważna w porównaniu do NP-hard?

Badam złożoność obliczeniową i zastanawiałem się, dlaczego problemy z NP-Complete (NPC) są w ogóle ważną klasą. Wydaje mi się oczywiste, dlaczego chcemy pokazać, że dany problem NP jest trudny do przeprowadzenia.

Rozumiem też definicję NPC, a pokazanie danego problemu decyzyjnego jest trudne dla NP, wiedząc, że jest w NP, jest dokładnie tym, co oznacza NPC.

Nie rozumiem jednak: dlaczego ta koncepcja jest tak ważna? Z pewnością, gdy się znaleźć żadnych NP-trudny algorytm, który jest uruchamiany w czasie P (czy to w NP), wykazano, że .$NP = P$

Dlaczego ta koncepcja jest tak ważna?

Istnieje co najmniej kilka powodów, dla których NPC jest interesujący:

• Klasa NP zawiera wiele interesujących problemów (zarówno praktycznych, jak i teoretycznych), ponadto wiele z tych problemów okazuje się trudnych do NP (a zatem NP-zupełnych), ale wiele problemów poza NP jest prawie na pewno zbyt trudnych więcej niż teoretyczne zainteresowanie , więc NPC zapewnia (szorstką) grupę problemów, które najwyraźniej są trudne, ale nie tak trudne, że nie możemy spróbować z nimi zrobić.
  Innymi słowy, NPC jest prawdopodobnie granicą tego, co mamy nadzieję, że może być rozwiązane w czasie wielomianowym, wydaje się, że próba PSPACE = P (na przykład) wydaje się trudna.
• Klasa NP jest interesująca strukturalnie. Jest to podstawowy przykład „czy otrzymujemy więcej obliczeniowej„ prędkości ”z niedeterminizmu”. Jesteśmy więc zainteresowani, czy P = NP, czy nie, a NPC jest (prawdopodobnie) ważnym składnikiem tego rozwiązania.
• NP-trudny (jako klasa) jest naprawdę zbyt duży i zróżnicowany, aby poradzić sobie jako jedna rzecz, to wszystko, co można zredukować z problemu NP-zupełnego , w tym ogromnego obszaru rzeczy poza NP, więc od punktu biorąc pod uwagę próbę opracowania ogólnych wyników i technik, nie ma się do czego przyczepić.

Z punktu widzenia kogoś, kto pisze kod życia, dobra znajomość kompletności NP jest ważna dla:

1. Rozpoznawanie, kiedy szczekasz na niewłaściwe drzewo

Problemy z NP-zupełnym są najłatwiejszym z problemów trudnych z NP, a jednak, o ile wiemy, potrzeba czasu wykładniczo do wielkości danych wejściowych, aby rozwiązać taki problem decyzyjny. Tak więc, jeśli możesz wykazać, że problem, który próbujesz rozwiązać, jest trudny do rozwiązania w NP (zazwyczaj przez wykazanie, że skuteczne rozwiązanie zapewniłoby również skuteczne rozwiązanie problemu z NP-zupełnym), wiesz, że możesz przestać szukać wydajnego algorytmu, aby go rozwiązać dokładnie w ogóle. Zamiast tego możesz wybierać spośród znanych algorytmów, które obiecują dobre przybliżenie problemów związanych z optymalizacją NP-hard i zająć się resztą projektu.

2. Znalezienie odpowiedniego drzewa

Ponieważ komputery są często wykorzystywane do atakowania problemów trudnych dla NP, opracowano wyspecjalizowane solwery, które mogą skutecznie rozwiązywać niektóre problemy trudne dla NP. Uznanie, że twój problem jest NP-zupełny, jest pierwszym krokiem do znalezienia istniejącego narzędzia (SAT, ILP, SMT, CSP, żeby wymienić tylko kilka), które mogą pomóc ci znaleźć dokładne rozwiązania w niektórych przypadkach, w których inaczej musiałbyś zadowolić się przybliżenie.

„Z pewnością, jeśli znajdziemy jakiś algorytm trudny dla NP, który działa w czasie P (niezależnie od tego, czy jest to NP), pokazaliśmy, że NP = P. Dlaczego ta koncepcja jest tak ważna?”

Każdy problem NP redukuje się do dowolnego problemu NPC, ale nie jest prawdą, że każdy problem NP ogranicza się do dowolnego problemu trudnego dla NP, więc udowodnienie, że algorytm NP-twardy jest w P, wcale nie dowodzi, że P = NP w ogóle. Byłoby tak jednak w przypadku problemu NPC, właśnie to oznacza „redukcja”. Jeśli więc znajdziemy algorytm P dla problemu NPC, udowodnimy, że P = NP.