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

Niech ${\displaystyle P}$ będzie dowolnym wielomianem, a ${\displaystyle \pi }$ problemem decyzyjnym. Oznaczając przez ${\displaystyle \pi _{P}}$ podproblem problemu ${\displaystyle \pi }$ otrzymany przez ograniczenie dziedziny ${\displaystyle \pi }$ do tych instancji, dla których:

${\displaystyle \max(I)\leqslant P(n(I)),}$

gdzie:

${\displaystyle \max(I)}$ oznacza największą liczbę występującą w opisie ${\displaystyle I,}$

${\displaystyle n(I)}$ rozmiar instancji ${\displaystyle I.}$

Można powiedzieć, że problem decyzyjny ${\displaystyle \pi }$ jest silnie NP-zupełny, jeśli ${\displaystyle \pi }$ jest NP i istnieje taki wielomian ${\displaystyle P,}$ że ${\displaystyle \pi _{P}}$ jest NP-zupełny.

Z definicji tej od razu wynika, że jeśli ${\displaystyle \pi }$ jest NP-zupełny i nie jest 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 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

Następujące 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ł,
• problem kolorowania grafu.

Zobacz też

• problem NP-trudny
• problem obliczeniowy