Pojęcie '''transformacji pseudowielomianowej''' ma zastosowanie w dowodzeniu [[Problem silnie NP zupełny|silnej NP-zupełności]] [[Problem decyzyjny|problemów decyzyjnych]]. Dowody takie opierają się na twierdzeniu, zgodnie z którym jeśli problem π<sub>2</sub> jest [[Problem silnie NP zupełny|silnie NP-zupełny]] i istnieje '''transformacja pseudowielomianowa''' problemu π<sub>2</sub> do problemu π<sub>1</sub> oraz <math>\pi_1 \in NP</math> to problem π<sub>1</sub> jest [[Problem silnie NP zupełny|silnie NP-zupełny]]. Wystarczy więc znaleźć problem [[Problem silnie NP zupełny|silnie NP-zupełny]] i przetransformowac go pseudowielomianowo do problemu, którego [[Problem silnie NP zupełny|silną NP-zupełność]] chcemy dowieść.