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.^[1]

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

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

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

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

A pseudo-polynomial transformation from ${\displaystyle \Pi _{1}}${\displaystyle \Pi _{1}} to ${\displaystyle \Pi _{2}}${\displaystyle \Pi _{2}} is a function ${\displaystyle f:\Sigma _{1}\to \Sigma _{2}}${\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}}${\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)}${\displaystyle \forall w\in \Sigma _{1}\quad f(w)} can be computed in time polynomial in two variables ${\displaystyle \operatorname {Num} _{\Pi _{1}}(w)}${\displaystyle \operatorname {Num} _{\Pi _{1}}(w)} and ${\displaystyle |w|}${\displaystyle |w|}
3. ${\displaystyle \exists Q_{A}\in \mathbb {N} [X]\quad \forall w\in \Sigma _{1}\quad |w|\leq Q_{A}(|f(w)|)}${\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|)}${\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}}${\displaystyle \Pi _{1}} in terms of instances of ${\displaystyle \Pi _{2}}${\displaystyle \Pi _{2}} (and back), (2) ensures that deciding ${\displaystyle L_{1}}${\displaystyle L_{1}} using the transformation and a pseudo-polynomial decider for ${\displaystyle L_{2}}${\displaystyle L_{2}} is pseudo-polynomial itself, (3) enforces that ${\displaystyle f}${\displaystyle f} grows fast enough so that ${\displaystyle L_{2}}${\displaystyle L_{2}} must have a pseudo-polynomial decider, and (4) enforces that a subproblem of ${\displaystyle L_{1}}${\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}}${\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}}${\displaystyle \Pi _{1}} is a strongly NP-complete decision problem, ${\displaystyle \Pi _{2}}${\displaystyle \Pi _{2}} is a decision problem in NP, and there exists a pseudo-polynomial transformation from ${\displaystyle \Pi _{1}}${\displaystyle \Pi _{1}} to ${\displaystyle \Pi _{2}}${\displaystyle \Pi _{2}}, then ${\displaystyle \Pi _{2}}${\displaystyle \Pi _{2}} is strongly NP-complete

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

Let ${\displaystyle f:L_{1}\to L_{2}}${\displaystyle f:L_{1}\to L_{2}} be a pseudo-polynomial transformation from ${\displaystyle \Pi _{1}}${\displaystyle \Pi _{1}} to ${\displaystyle \Pi _{2}}${\displaystyle \Pi _{2}} with ${\displaystyle Q_{A}}${\displaystyle Q_{A}}, ${\displaystyle Q_{B}}${\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]}${\displaystyle P\in \mathbb {N} [X]} such that ${\displaystyle L_{1/P}=\{w\in L_{1}:\operatorname {Num} _{\Pi _{1}}(w)\leq P(|w|)\}}${\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))}${\displaystyle {\widehat {P}}(n)=Q_{B}(P(Q_{A}(n)),Q_{A}(n))} and any ${\displaystyle w\in L_{1/P}}${\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}}}${\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}}}}${\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}}${\displaystyle L_{1/P}} is NP-complete and ${\displaystyle f|L_{1/P}}${\displaystyle f|L_{1/P}} is computable in polynomial time, ${\displaystyle L_{2/{\widehat {P}}}}${\displaystyle L_{2/{\widehat {P}}}} is NP-complete.

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