Problem NP-trudny


Problem NP-trudny w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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 π 2 {\displaystyle \pi _{2}} jest NP-trudny, jeżeli pewien problem NP-zupełny π 1 {\displaystyle \pi _{1}} jest do niego redukowalny wielomianową transformacją Turinga.

Innymi słowy, problem NP-zupełny π 1 {\displaystyle \pi _{1}} można rozwiązać w wielomianowym czasie algorytmem rozwiązującym problem NP-trudny π 2 , {\displaystyle \pi _{2},} przez wykorzystanie hipotetycznej procedury H {\displaystyle H} sprowadzającej problem NP-zupełny π 1 {\displaystyle \pi _{1}} do problemu NP-trudnego π 2 , {\displaystyle \pi _{2},} jeżeli tylko H {\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 π 2 {\displaystyle \pi _{2}} jest co najmniej tak trudny, jak problem π 1 ; {\displaystyle \pi _{1};}
  • ponieważ π 1 {\displaystyle \pi _{1}} jest problemem NP-zupełnym, toteż należy on do problemów najtrudniejszych w klasie NP, dlatego NP-trudny problem π 2 {\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 π 2 ; {\displaystyle \pi _{2};}
  • ponadto, jeśli P N P , {\displaystyle P\neq NP,} to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym, natomiast rozstrzygnięcie P = N P {\displaystyle P=NP} nie przesądza o wielomianowej rozwiązywalności wszystkich problemów NP-trudnych;
  • jeżeli problem π 2 {\displaystyle \pi _{2}} należy do klasy NP, to π 2 {\displaystyle \pi _{2}} jest też problemem NP-zupełnym (gdyż wraz z istniejącą transformacją Turinga spełnia definicję problemu NP-zupełnego).

Spis treści

Przykłady | edytuj kod

Zobacz też | edytuj kod

Ważne klasy złożoności

Bibliografia | edytuj kod

  • 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 | edytuj kod

Na podstawie artykułu: "Problem NP-trudny" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy