Tekst źródłowy strony Problem silnie NP-zupełny

'''Problem silnie NP-zupełny''' ({{Ang.|Strongly NP-Complete}}) – [[problem decyzyjny (teoria obliczeń)|problem decyzyjny]], który nawet przy ograniczeniu maksymalnej wartości występujących w jego opisie liczb pozostaje [[Problem NP-zupełny|NP-zupełny]].

Istnienie [[Algorytm pseudowielomianowy|algorytmu pseudowielomianowego]] dla dowolnego problemu silnie NP-zupełnego implikowałoby równość [[Problem P|P]]=[[Problem NP|NP]], a więc jest uważane za wysoce nieprawdopodobne. Natomiast problemy silnie NP-zupełne pozostałyby NP-zupełne nawet przy [[Kod unarny|kodowaniu unarnym]], stąd też są również znane jako problemy '''jedynkowo NP-zupełne'''.

== Definicja formalna ==
Niech <math>P</math> będzie dowolnym wielomianem, a <math>\pi</math> [[Problem decyzyjny (teoria obliczeń)|problemem decyzyjnym]]. Oznaczając przez <math>\pi_P</math> podproblem problemu <math>\pi</math> otrzymany przez ograniczenie dziedziny <math>\pi</math> do tych instancji, dla których:
: <math>\max(I) \leqslant P(n(I)),</math>

gdzie:
: <math>\max(I)</math> oznacza największą liczbę występującą w opisie <math>I,</math>
: <math>n(I)</math> rozmiar instancji <math>I.</math>

Można powiedzieć, że problem decyzyjny <math>\pi</math> jest silnie NP-zupełny, jeśli <math>\pi</math> jest [[Problem NP|NP]] i istnieje taki wielomian <math>P,</math> że <math>\pi_P</math> jest [[Problem NP-zupełny|NP-zupełny]].

Z definicji tej od razu wynika, że jeśli <math>\pi</math> jest NP-zupełny i nie jest [[Problem liczbowy|problemem liczbowym]], to jest silnie NP-zupełny.

== Dowodzenie silnej NP-zupełności ==
Dowodzenie silnej NP-zupełności bezpośrednio z definicji wymagałoby znalezienia [[wielomian]]u spełniającego warunki określone w definicji. Niejednokrotnie okazuje się to jednak niełatwe.

W przypadku problemów, które nie są problemami liczbowymi wystarczy jednak dowieść tylko ich [[Problem NP-zupełny|NP-zupełności]]. Zaś w przypadku problemów liczbowych wykorzystuje się [[Transformacja pseudowielomianowa|transformacje pseudowielomianowe]] do sprowadzenia pewnego znanego problemu silnie NP-zupełnego do danego problemu, którego silną NP-zupełność się dowodzi, podobnie jak wykorzystuje się [[Transformacja wielomianowa|transformacje wielomianowe]] przy dowodzeniu NP-zupełności.

== Przykłady ==
Następujące [[Problem liczbowy|problemy liczbowe]] są silnie NP-zupełne:
* [[problem komiwojażera]],
* [[problem podziału zbioru na trójelementowe podzbiory]].

Następujące problemy niebędące problemami liczbowymi są silnie NP-zupełne:
* [[problem spełnialności]] formuł,
* [[Kolorowanie grafu|problem kolorowania grafu]].

== Zobacz też ==
* [[problem NP-trudny]]
* [[problem obliczeniowy]]

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