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

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

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

Pseudo-polynomial transformation

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

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

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

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

Proof of the lemma

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

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

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

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

${\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,

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

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

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