Problem silnie NP-zupełny

Z Wikipedii

Problemy silnie NP-zupełne to takie problemy decyzyjne, które nawet przy ograniczeniu maksymalnej wartości występujacych w ich opisie liczb pozostają NP-zupełne.

Istnienie algorytmu pseudowielomianowego dla dowolnego problemu silnie NP-zupełnego implikowałoby równość P=NP, a więc jest uważane za wysoce nieprawdopodobne.

Problemy silnie NP-zupełne pozostałyby NP-zupełne nawet przy kodowaniu unarnym, stąd też są również znane jako problemy jedynkowo NP-zupełne.

[edytuj] Definicja formalna

Niech P będzie dowolnym wielomianem a π problemem decyzyjnym. Oznaczmy przez π_P podproblem problemu π otrzymany przez ograniczenie dziedziny π do tych instancji, dla których

$\max(I) \leq P(n(I))$

gdzie max(I) oznacza największą liczbę występującą w opisie I a n(I) rozmiar instancji I.

Powiemy, ze problem decyzyjny π jest silnie NP-zupełny jeśli π jest NP i istnieje taki wielomian P, ze π_P jest NP-zupełny.

Z definicji tej od razu wynika, że jeśli π jest NP-zupełny i nie jest problemem liczbowym to jest silnie NP-zupełny.

[edytuj] Dowodzenie silnej NP-zupełności

Dowodzenie silnej NP-zupełności bezpośrednio z definicji wymagałoby znalezienia wielomianu spełniającego warunki określone w definicji. Niejednokrotnie okazuje sie to jednak niełatwe.

W przypadku problemów, które nie są problemami liczbowymi wystarczy jednak dowieść ich NP-zupełności.

W przypadku zaś problemów liczbowych wykorzystuje się 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ę transformacje wielomianowe przy dowodzeniu NP-zupełności.