Problem silnie NP-zupełny
Problem silnie NP-zupełny (ang. Strongly NP-Complete) to taki problem decyzyjny, który nawet przy ograniczeniu maksymalnej wartości występujących w jego opisie liczb pozostaje NP-zupełny.
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. Natomiast 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.
Definicja formalna
[edytuj | edytuj kod]Niech będzie dowolnym wielomianem, a problemem decyzyjnym. Oznaczając przez podproblem problemu otrzymany przez ograniczenie dziedziny do tych instancji, dla których:
gdzie:
- oznacza największą liczbę występującą w opisie
- rozmiar instancji
Można powiedzieć, że problem decyzyjny jest silnie NP-zupełny, jeśli jest NP i istnieje taki wielomian że 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.
Dowodzenie silnej NP-zupełności
[edytuj | edytuj kod]Dowodzenie silnej NP-zupełności bezpośrednio z definicji wymagałoby znalezienia wielomianu 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 NP-zupełności. Zaś w przypadku 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.
Przykłady
[edytuj | edytuj kod]Następujące problemy liczbowe są silnie NP-zupełne:
Następujące problemy niebędące problemami liczbowymi są silnie NP-zupełne: