Problem NP-trudny

Problem NP-trudny (NPH, ang. NP-Hard) – problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne, jak rozwiązanie każdego problemu z klasy NP (całej klasy NP).

Formalna definicja problemu NP-trudnego jest następująca:

Problem ${\displaystyle \pi _{2}}$ jest NP-trudny, jeżeli pewien problem NP-zupełny ${\displaystyle \pi _{1}}$ jest do niego redukowalny wielomianową transformacją Turinga.

Innymi słowy, problem NP-zupełny ${\displaystyle \pi _{1}}$ można rozwiązać w wielomianowym czasie algorytmem rozwiązującym problem NP-trudny ${\displaystyle \pi _{2},}$ przez wykorzystanie hipotetycznej procedury ${\displaystyle H}$ sprowadzającej problem NP-zupełny ${\displaystyle \pi _{1}}$ do problemu NP-trudnego ${\displaystyle \pi _{2},}$ jeżeli tylko ${\displaystyle H}$ daje się wykonać w wielomianowym czasie. NP-trudność można zdefiniować także w kategorii języków formalnych (a nie problemów). Do klasy problemów NP-trudnych mogą należeć problemy różnego typu: decyzyjne, przeszukiwania, optymalizacyjne.

Wraz z definicjami klas problemów NP i NP-zupełnych ma to następujące konsekwencje:

• problem optymalizacyjny, którego wersja decyzyjna jest NP-zupełna, jest problemem NP-trudnym;

• NP-trudny problem ${\displaystyle \pi _{2}}$ jest co najmniej tak trudny, jak problem ${\displaystyle \pi _{1};}$

• ponieważ ${\displaystyle \pi _{1}}$ jest problemem NP-zupełnym, toteż należy on do problemów najtrudniejszych w klasie NP, dlatego NP-trudny problem ${\displaystyle \pi _{2}}$ jest co najmniej tak trudny, jak cała klasa NP;

• ponieważ wszystkie problemy NP-zupełne transformują się wzajemnie do siebie (zwykłą) transformacją wielomianową (nie Turinga), to również wszystkie problemy NP-zupełne można rozwiązać przez redukcję do NP-trudnego problemu ${\displaystyle \pi _{2};}$

• ponadto, jeśli ${\displaystyle P\neq NP,}$ to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym, natomiast rozstrzygnięcie ${\displaystyle P=NP}$ nie przesądza o wielomianowej rozwiązywalności wszystkich problemów NP-trudnych;

• jeżeli problem ${\displaystyle \pi _{2}}$ należy do klasy NP, to ${\displaystyle \pi _{2}}$ jest też problemem NP-zupełnym (gdyż wraz z istniejącą transformacją Turinga spełnia definicję problemu NP-zupełnego).

Przykłady

• problem komiwojażera
• problem plecakowy
• problem zbioru niezależnego
• problem zbioru wierzchołków rozrywających cykle

Zobacz też

• algorytm pseudowielomianowy
• problem liczbowy
• problem silnie NP-zupełny

Bibliografia

• M. R. Garey, D. S. Johnson, Computers and Intractability: A guide to the Theory of NP-Completeness, W.H.Freeman and Co., San Francisco, 1979.
• Christos H. Papadimitriou, Złożoność obliczeniowa, WNT, 2002.
• T. H. Cormen, C. E. Leiserson, C. Stein i R. L. Rivest, Wprowadzenie do algorytmów, WNT, 2004
• M. Kubale, Łagodne wprowadzenie do analizy algorytmów, Wydawnictwo Politechniki Gdańskiej, 2004.

Linki zewnętrzne

• The Complexity Zoo. complexityzoo.uwaterloo.ca. [zarchiwizowane z tego adresu (2019-08-27)].