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.

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 ${\displaystyle {\sqrt {n}}}$in ${\displaystyle {\sqrt {n}}-1}$divisions, therefore exponentially more than the input size ${\displaystyle O(\log(n))}$. Suppose that ${\displaystyle L}$is an encoding of a computational problem ${\displaystyle \Pi }$over alphabet ${\displaystyle \Sigma }$, then

${\displaystyle \operatorname {Num} _{\Pi }:\Sigma ^{*}\to \mathbb {N} }$

is a function that maps ${\displaystyle w_{I}\in \Sigma ^{*}}$, being the encoding of an instance ${\displaystyle I}$of the problem ${\displaystyle \Pi }$, to the maximal numerical parameter of ${\displaystyle I}$.

Suppose that ${\displaystyle \Pi _{1}}$and ${\displaystyle \Pi _{2}}$are decision problems, ${\displaystyle L_{1}}$and ${\displaystyle L_{2}}$are their encodings over correspondingly ${\displaystyle \Sigma _{1}}$and ${\displaystyle \Sigma _{2}}$alphabets.

A pseudo-polynomial transformation from ${\displaystyle \Pi _{1}}$to ${\displaystyle \Pi _{2}}$is a function ${\displaystyle f:\Sigma _{1}\to \Sigma _{2}}$such that

1. ${\displaystyle \forall w\in \Sigma _{1}\quad w\in L_{1}\iff f(w)\in L_{2}}$
2. ${\displaystyle \forall w\in \Sigma _{1}\quad f(w)}$can be computed in time polynomial in two variables ${\displaystyle \operatorname {Num} _{\Pi _{1}}(w)}$and ${\displaystyle |w|}$
3. ${\displaystyle \exists Q_{A}\in \mathbb {N} [X]\quad \forall w\in \Sigma _{1}\quad |w|\leq Q_{A}(|f(w)|)}$
4. ${\displaystyle \exists Q_{B}\in \mathbb {N} [X,Y]\quad \forall w\in \Sigma _{1}\quad \operatorname {Num} _{\Pi _{2}}(f(w))\leq Q_{B}(\operatorname {Num} _{\Pi _{1}}(w),|w|)}$

Intuitively, (1) allows one to reason about instances of ${\displaystyle \Pi _{1}}$in terms of instances of ${\displaystyle \Pi _{2}}$(and back), (2) ensures that deciding ${\displaystyle L_{1}}$using the transformation and a pseudo-polynomial decider for ${\displaystyle L_{2}}$is pseudo-polynomial itself, (3) enforces that ${\displaystyle f}$grows fast enough so that ${\displaystyle L_{2}}$must have a pseudo-polynomial decider, and (4) enforces that a subproblem of ${\displaystyle L_{1}}$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 ${\displaystyle L_{2}}$whose instances also have numerical parameters bounded by a polynomial in input size.

The following lemma allows to derive strong NP-completeness from existence of a transformation:

If ${\displaystyle \Pi _{1}}$is a strongly NP-complete decision problem, ${\displaystyle \Pi _{2}}$is a decision problem in NP, and there exists a pseudo-polynomial transformation from ${\displaystyle \Pi _{1}}$to ${\displaystyle \Pi _{2}}$, then ${\displaystyle \Pi _{2}}$is strongly NP-complete

Suppose that ${\displaystyle \Pi _{1}}$is a strongly NP-complete decision problem encoded by ${\displaystyle L_{1}}$over ${\displaystyle \Sigma _{1}}$alphabet and ${\displaystyle \Pi _{2}}$is a decision problem in NP encoded by ${\displaystyle L_{2}}$over ${\displaystyle \Sigma _{2}}$alphabet.

Let ${\displaystyle f:L_{1}\to L_{2}}$be a pseudo-polynomial transformation from ${\displaystyle \Pi _{1}}$to ${\displaystyle \Pi _{2}}$with ${\displaystyle Q_{A}}$, ${\displaystyle Q_{B}}$as specified in the definition.

From the definition of strong NP-completeness there exists a polynomial ${\displaystyle P\in \mathbb {N} [X]}$such that ${\displaystyle L_{1/P}=\{w\in L_{1}:\operatorname {Num} _{\Pi _{1}}(w)\leq P(|w|)\}}$is NP-complete.

For ${\displaystyle {\widehat {P}}(n)=Q_{B}(P(Q_{A}(n)),Q_{A}(n))}$and any ${\displaystyle w\in L_{1/P}}$there is

${\displaystyle {\begin{aligned}\operatorname {Num} _{\Pi _{2}}(f(w))&\leq Q_{B}(\operatorname {Num} _{\Pi _{1}}(w),|w|)&&{\text{(definition of }}f{\text{)}}\\[4pt]&\leq Q_{B}(P(w),|w|)&&{\text{(property of }}L_{1/P}{\text{)}}\\[4pt]&\leq Q_{B}(P(Q_{A}(|f(w)|)),Q_{A}(|f(w)|))&&{\text{(definition of }}f{\text{)}}\\[4pt]&\leq {\widehat {P}}(|f(w)|)&&{\text{(definition of }}{\widehat {P}}{\text{)}}\end{aligned}}}$

Therefore,

${\displaystyle f(L_{1/P})=\{w\in L_{2}:\operatorname {Num} _{\Pi _{2}}(w)\leq {\widehat {P}}(|w|)\}=L_{2/{\widehat {P}}}}$

Since ${\displaystyle L_{1/P}}$is NP-complete and ${\displaystyle f|L_{1/P}}$is computable in polynomial time, ${\displaystyle L_{2/{\widehat {P}}}}$is NP-complete.

From this and the definition of strong NP-completeness it follows that ${\displaystyle L_{2}}$is strongly NP-complete.