Pseudo-polynomial transformation

Short description: Function used in computational complexity theory

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

[math]\displaystyle{ \operatorname{Num}_\Pi: \Sigma^* \to \mathbb{N} }[/math]

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

Pseudo-polynomial transformation

Suppose that [math]\displaystyle{ \Pi_1 }[/math] and [math]\displaystyle{ \Pi_2 }[/math] are decision problems, [math]\displaystyle{ L_1 }[/math] and [math]\displaystyle{ L_2 }[/math] are their encodings over correspondingly [math]\displaystyle{ \Sigma_1 }[/math] and [math]\displaystyle{ \Sigma_2 }[/math] alphabets.

A pseudo-polynomial transformation from [math]\displaystyle{ \Pi_1 }[/math] to [math]\displaystyle{ \Pi_2 }[/math] is a function [math]\displaystyle{ f: \Sigma_1 \to \Sigma_2 }[/math] such that

1. [math]\displaystyle{ \forall w \in \Sigma_1 \quad w \in L_1 \iff f(w) \in L_2 }[/math]
2. [math]\displaystyle{ \forall w \in \Sigma_1 \quad f(w) }[/math] can be computed in time polynomial in two variables [math]\displaystyle{ \operatorname{Num}_{\Pi_1}(w) }[/math] and [math]\displaystyle{ |w| }[/math]
3. [math]\displaystyle{ \exists Q_A \in \mathbb{N}[X] \quad\forall w \in \Sigma_1 \quad |w| \leq Q_A(|f(w)|) }[/math]
4. [math]\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|) }[/math]

Intuitively, (1) allows one to reason about instances of [math]\displaystyle{ \Pi_1 }[/math] in terms of instances of [math]\displaystyle{ \Pi_2 }[/math] (and back), (2) ensures that deciding [math]\displaystyle{ L_1 }[/math] using the transformation and a pseudo-polynomial decider for [math]\displaystyle{ L_2 }[/math] is pseudo-polynomial itself, (3) enforces that [math]\displaystyle{ f }[/math] grows fast enough so that [math]\displaystyle{ L_2 }[/math] must have a pseudo-polynomial decider, and (4) enforces that a subproblem of [math]\displaystyle{ L_1 }[/math] 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 [math]\displaystyle{ L_2 }[/math] 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 [math]\displaystyle{ \Pi_1 }[/math] is a strongly NP-complete decision problem, [math]\displaystyle{ \Pi_2 }[/math] is a decision problem in NP, and there exists a pseudo-polynomial transformation from [math]\displaystyle{ \Pi_1 }[/math] to [math]\displaystyle{ \Pi_2 }[/math], then [math]\displaystyle{ \Pi_2 }[/math] is strongly NP-complete

Proof of the lemma

Suppose that [math]\displaystyle{ \Pi_1 }[/math] is a strongly NP-complete decision problem encoded by [math]\displaystyle{ L_1 }[/math] over [math]\displaystyle{ \Sigma_1 }[/math] alphabet and [math]\displaystyle{ \Pi_2 }[/math] is a decision problem in NP encoded by [math]\displaystyle{ L_2 }[/math] over [math]\displaystyle{ \Sigma_2 }[/math] alphabet.

Let [math]\displaystyle{ f: L_1 \to L_2 }[/math] be a pseudo-polynomial transformation from [math]\displaystyle{ \Pi_1 }[/math] to [math]\displaystyle{ \Pi_2 }[/math] with [math]\displaystyle{ Q_A }[/math], [math]\displaystyle{ Q_B }[/math] as specified in the definition.

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

For [math]\displaystyle{ \widehat{P}(n) = Q_B(P(Q_A(n)),Q_A(n)) }[/math] and any [math]\displaystyle{ w \in L_{1/P} }[/math] there is

[math]\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} }[/math]

Therefore,

[math]\displaystyle{ f(L_{1/P}) = \{w \in L_2 : \operatorname{Num}_{\Pi_2}(w) \leq \widehat{P}(|w|) \} = L_{2/\widehat{P}} }[/math]

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

From this and the definition of strong NP-completeness it follows that [math]\displaystyle{ L_2 }[/math] is strongly NP-complete.