Tekst źródłowy strony 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 [[Problem NP|NP]] (całej klasy NP).

Formalna definicja problemu '''NP-trudnego''' jest następująca:
: ''Problem <math>\pi_2</math> jest''' NP-trudny,''' jeżeli pewien [[problem NP-zupełny]] <math>\pi_1</math> jest do niego redukowalny wielomianową [[transformacja Turinga|transformacją Turinga]].''

Innymi słowy, problem NP-zupełny <math>\pi_1</math> można rozwiązać w wielomianowym czasie algorytmem rozwiązującym problem NP-trudny <math>\pi_2,</math> przez wykorzystanie hipotetycznej procedury <math>H</math> sprowadzającej problem NP-zupełny <math>\pi_1</math> do problemu NP-trudnego <math>\pi_2,</math> jeżeli tylko <math>H</math> daje się wykonać w wielomianowym czasie. '''NP-trudność''' można zdefiniować także w kategorii [[język formalny|języków formalnych]] (a nie problemów). Do klasy problemów NP-trudnych mogą należeć problemy różnego typu: [[problem decyzyjny (teoria obliczeń)|decyzyjne]], [[problem przeszukiwania (teoria obliczeń)|przeszukiwania]], [[Problem optymalizacyjny|optymalizacyjne]].

Wraz z definicjami klas problemów [[Problem NP|NP]] i [[Problem NP-zupełny|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 <math>\pi_2</math> jest co najmniej tak trudny, jak problem <math>\pi_1;</math>
* ponieważ <math>\pi_1</math> jest problemem NP-zupełnym, toteż należy on do problemów najtrudniejszych w klasie [[Problem NP|NP]], dlatego '''NP-trudny''' problem <math>\pi_2</math> 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 <math>\pi_2;</math>
* ponadto, jeśli <math>P \neq NP,</math> to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym, natomiast rozstrzygnięcie <math>P = NP</math> nie przesądza o wielomianowej rozwiązywalności wszystkich problemów NP-trudnych;
* jeżeli problem <math>\pi_2</math> należy do klasy NP, to <math>\pi_2</math> 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]]

{{klasy złożoności}}

== 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 ==
* {{Cytuj stronę |url = https://complexityzoo.uwaterloo.ca/Complexity_Zoo |tytuł = The Complexity Zoo |opublikowany = complexityzoo.uwaterloo.ca |archiwum = https://web.archive.org/web/20190827233504/https://complexityzoo.uwaterloo.ca/Complexity_Zoo |zarchiwizowano = 2019-08-27}}

{{Kontrola autorytatywna}}

[[Kategoria:Klasy złożoności]]