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
Kategoria:Klasy złożoności