Problem silnie NP-zupełny

Problem silnie NP-zupełny

Problem silnie NP-zupełny to problem decyzyjny, który pozostaje NP-zupełny nawet przy ograniczeniu wartości liczbowych w jego opisie. Uznaje się, że istnienie algorytmu pseudowielomianowego dla takiego problemu implikowałoby równość P=NP, co jest wysoce nieprawdopodobne. Problemy te są również nazywane problemami jedynkowo NP-zupełnymi, ponieważ pozostają NP-zupełne nawet przy kodowaniu unarnym.

Definicja formalna

Niech $P$ będzie wielomianem, a $pi$ problemem decyzyjnym. Podproblem $pi\_P$ powstaje poprzez ograniczenie dziedziny $pi$ do instancji spełniających warunek:

$max(I)\; leqslant\; P(n(I))$,

gdzie $max(I)$ to największa liczba w opisie $I$, a $n(I)$ to rozmiar instancji. Problem $pi$ jest silnie NP-zupełny, jeśli jest NP i istnieje wielomian $P$, dla którego $pi\_P$ jest NP-zupełny. Z definicji wynika, że jeśli $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 wymaga znalezienia odpowiedniego wielomianu. Dla problemów nieliczbowych wystarczy wykazać NP-zupełność, natomiast w przypadku problemów liczbowych stosuje się transformacje pseudowielomianowe, aby sprowadzić znany problem silnie NP-zupełny do badanego problemu.

Przykłady

Problemy silnie NP-zupełne obejmują:

• problem komiwojażera,
• problem podziału zbioru na trójelementowe podzbiory.

Przykłady problemów nieliczbowych, które są silnie NP-zupełne to:

• problem spełnialności formuł,
• problem kolorowania grafu.