Pseudo-polynomial transformation

In computational complexity theory, a pseudo-polynomial transformation is a function which maps instances of one strongly NP-complete problem into another and is computable in pseudo-polynomial time.
Definitions.
Maximal numerical parameter.
Some computational problems are parameterized by numbers whose magnitude exponentially exceed size of the input. For example, the problem of testing whether a number "n" is prime can be solved by naively checking candidate factors from 2 to formula_1 in formula_2 divisions, therefore exponentially more than the input size formula_3. Suppose that formula_4 is an encoding of a computational problem formula_5 over alphabet formula_6, then
is a function that maps formula_8, being the encoding of an instance formula_9 of the problem formula_5, to the maximal numerical parameter of formula_9.
Pseudo-polynomial transformation.
Suppose that formula_12 and formula_13 are decision problems, formula_14 and formula_15 are their encodings over correspondingly formula_16 and formula_17 alphabets.
A pseudo-polynomial transformation from formula_12 to formula_13 is a function formula_20 such that
Intuitively, (1) allows one to reason about instances of formula_12 in terms of instances of formula_13 (and back), (2) ensures that deciding formula_14 using the transformation and a pseudo-polynomial decider for formula_15 is pseudo-polynomial itself, (3) enforces that formula_31 grows fast enough so that formula_15 must have a pseudo-polynomial decider, and (4) enforces that a subproblem of formula_14 that testifies its strong NP-completeness (i.e. all instances have numerical parameters bounded by a polynomial in input size and the subproblem is NP-complete itself) is mapped to a subproblem of formula_15 whose instances also have numerical parameters bounded by a polynomial in input size.
Proving strong NP-completeness.
The following lemma allows to derive strong NP-completeness from existence of a transformation:
Proof of the lemma.
Suppose that formula_12 is a strongly NP-complete decision problem encoded by formula_14 over formula_16 alphabet and formula_13 is a decision problem in NP encoded by formula_15 over formula_17 alphabet.
Let formula_46 be a pseudo-polynomial transformation from formula_12 to formula_13 with formula_49, formula_50 as specified in the definition.
From the definition of strong NP-completeness there exists a polynomial formula_51 such that formula_52 is NP-complete.
For formula_53 and any formula_54 there is
Therefore,
Since formula_57 is NP-complete and formula_58 is computable in polynomial time, formula_59 is NP-complete.
From this and the definition of strong NP-completeness it follows that formula_15 is strongly NP-complete.