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 $\mathrm{\Pi }$ over alphabet $\mathrm{\Sigma }$, then

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

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

Pseudo-polynomial transformation

Suppose that ${\mathrm{\Pi }}_1$ and ${\mathrm{\Pi }}_2$ are decision problems, $L_1$ and $L_2$ are their encodings over correspondingly ${\mathrm{\Sigma }}_1$ and ${\mathrm{\Sigma }}_2$ alphabets.

A pseudo-polynomial transformation from ${\mathrm{\Pi }}_1$ to ${\mathrm{\Pi }}_2$ is a function $f:{\mathrm{\Sigma }}_1\to {\mathrm{\Sigma }}_2$ such that

1. $\mathrm{\forall }w\in {\mathrm{\Sigma }}_{1}w\in L_1⟺f(w)\in L_2$
2. $\mathrm{\forall }w\in {\mathrm{\Sigma }}_{1}f(w)$ can be computed in time polynomial in two variables ${\mathrm{Num}}_{{\mathrm{\Pi }}_1}(w)$ and $|w|$
3. $\mathrm{\exists }{Q}_A\in \mathbb{N}[X]\mathrm{\forall }w\in {\mathrm{\Sigma }}_1|w|\le Q_A(|f(w)|)$
4. $\mathrm{\exists }{Q}_B\in \mathbb{N}[X,Y]\mathrm{\forall }w\in {\mathrm{\Sigma }}_1{\mathrm{Num}}_{{\mathrm{\Pi }}_2}(f(w))\le Q_B({\mathrm{Num}}_{{\mathrm{\Pi }}_1}(w),|w|)$

Intuitively, (1) allows one to reason about instances of ${\mathrm{\Pi }}_1$ in terms of instances of ${\mathrm{\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 ${\mathrm{\Pi }}_1$ is a strongly NP-complete decision problem, ${\mathrm{\Pi }}_2$ is a decision problem in NP, and there exists a pseudo-polynomial transformation from ${\mathrm{\Pi }}_1$ to ${\mathrm{\Pi }}_2$, then ${\mathrm{\Pi }}_2$ is strongly NP-complete

Proof of the lemma

Suppose that ${\mathrm{\Pi }}_1$ is a strongly NP-complete decision problem encoded by $L_1$ over ${\mathrm{\Sigma }}_1$ alphabet and ${\mathrm{\Pi }}_2$ is a decision problem in NP encoded by $L_2$ over ${\mathrm{\Sigma }}_2$ alphabet.

Let $f:L_1\to L_2$ be a pseudo-polynomial transformation from ${\mathrm{\Pi }}_1$ to ${\mathrm{\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:{\mathrm{Num}}_{{\mathrm{\Pi }}_1}(w)\le P(|w|)\}$ is NP-complete.

For $\hat{P}(n)=Q_B(P(Q_A(n)),Q_A(n))$ and any $w\in L_{1/P}$ there is

$\begin{array}{cccc}{\mathrm{Num}}_{{\mathrm{\Pi }}_2}(f(w))& \le Q_B({\mathrm{Num}}_{{\mathrm{\Pi }}_1}(w),|w|)& & \text{(definition of }f\text{)}\\ & \le Q_B(P(w),|w|)& & \text{(property of }{L}_{1/P}\text{)}\\ & \le Q_B(P(Q_A(|f(w)|)),Q_A(|f(w)|))& & \text{(definition of }f\text{)}\\ & \le \hat{P}(|f(w)|)& & \text{(definition of }\hat{P}\text{)}\end{array}$

Therefore,

$f(L_{1/P})=\{w\in L_2:{\mathrm{Num}}_{{\mathrm{\Pi }}_2}(w)\le \hat{P}(|w|)\}=L_{2/\hat{P}}$

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

From this and the definition of strong NP-completeness it follows that $L_2$ is strongly NP-complete.