Wolna encyklopedia

W teorii złożoności obliczeniowej problem NP-trudny (NPH) to taki problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne jak rozwiązanie każdego problemu z klasy NP.

Formalna definicja problemu NP-trudnego jest następująca: problem π₂ jest NP-trudny jeżeli pewien problem NP-zupełny π₁ jest do niego redukowalny wielomianową transformacją Turinga.

Innymi słowy, problem NP-zupełny π₁ można rozwiązać w wielomianowym czasie algorytmem rozwiązującym problem NP-trudny π₂, przez wykorzystanie hipotetycznej procedury H sprowadzającej problem NP-zupełny π₁ do problemu NP-trudnego π₂, jeżeli tylko H daje sie 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 π₂ jest co najmniej tak trudny jak problem π₁;

• ponieważ π₁ jest problemem NP-zupełnym dlatego należy on do klasy problemów najtrudniejszych w NP, dlatego NP-trudny problem π₂ 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 π₂;

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

• jeżeli problem π₂ należy do klasy NP, to π₂ jest też problem NP-zupełnym (gdyż wraz z istniejącą transformacją Turinga spełnia definicję problemu NP-zupełnego).

Przykłady

• Problem komiwojażera
• Problem plecakowy

Zobacz też

• Problem silnie NP-zupełny
• Problem liczbowy
• Algorytm pseudowielomianowy

Literatura

• 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: Introduction to Algorithms, The MIT Press/McGraw-Hill Company 1990 (wydanie polskie: Wprowadzenie do algorytmów, WNT 2004).
• M. Kubale: Łagodne wprowadzenie do analizy algorytmów, Gdańsk 2004.

Łącza zewnętrzne

• The Complexity Zoo