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 .
Dlaczego ta koncepcja jest tak ważna?
complexity-theory
np-complete
Amnestyczny
źródło
źródło
Odpowiedzi:
Istnieje co najmniej kilka powodów, dla których NPC jest interesujący:
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.
źródło
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.
źródło
„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.
źródło