The following lemma allows to derive strong NP-completeness from existence of a transformation:
Proof of the lemma
Suppose that is a strongly NP-complete decision problem encoded by over alphabet and is a decision problem in NP encoded by over alphabet.
Let be a pseudo-polynomial transformation from to with , as specified in the definition.
From the definition of strong NP-completeness there exists a polynomial such that is NP-complete.
For and any there is
Therefore,
Since is NP-complete and is computable in polynomial time, is NP-complete.
From this and the definition of strong NP-completeness it follows that is strongly NP-complete.