Misplaced Pages

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (November 2020) This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Pseudo-polynomial transformation" – news · newspapers · books · scholar · JSTOR (October 2018) (Learn how and when to remove this message)

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 ${\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}$.

Pseudo-polynomial transformation

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} \quad \forall w\in \Sigma _{1}\quad |w|\leq Q_{A}(|f(w)|)}$
4. ${\displaystyle \exists Q_{B}\in \mathbb {N} \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.

Proving strong NP-completeness

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

Proof of the lemma

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} }$ 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{)}}\\&\leq Q_{B}(P(w),|w|)&&{\text{(property of }}L_{1/P}{\text{)}}\\&\leq Q_{B}(P(Q_{A}(|f(w)|)),Q_{A}(|f(w)|))&&{\text{(definition of }}f{\text{)}}\\&\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.

References

1. Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. 101–102. ISBN 978-0-7167-1045-5. MR 0519066.

• Strongly NP-complete problems
• Complexity classes
• Computational complexity theory