Pseudo-polynomial transformation

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

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

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

Pseudo-polynomial transformation

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

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

1. ${\displaystyle \mathrm{\forall }w\in {\mathrm{\Sigma }}_{1}w\in L_1⟺f(w)\in L_2}$
2. ${\displaystyle \mathrm{\forall }w\in {\mathrm{\Sigma }}_{1}f(w)}$ can be computed in time polynomial in two variables ${\displaystyle {\mathrm{Num}}_{{\mathrm{\Pi }}_1}(w)}$ and ${\displaystyle |w|}$
3. ${\displaystyle \mathrm{\exists }{Q}_A\in \mathbb{N}[X]\mathrm{\forall }w\in {\mathrm{\Sigma }}_1|w|\le Q_A(|f(w)|)}$
4. ${\displaystyle \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 ${\displaystyle {\mathrm{\Pi }}_1}$ in terms of instances of ${\displaystyle {\mathrm{\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.