Dowody takie opierają się na twierdzeniu, zgodnie z którym jeśli problem jest silnie NP-zupełny i istnieje transformacja pseudowielomianowa problemu do problemu oraz to problem jest silnie NP-zupełny. Wystarczy więc znaleźć problem silnie NP-zupełny i przetransformować go pseudowielomianowo do problemu, którego silną NP-zupełność chcemy dowieść.
Zobacz też problem silnie NP zupełny
Kategoria:Teoria obliczeń