In computational complexity theory, a pseudo-polynomial transformation is a kind of reduction between decision problems that preserves strong NP-completeness. It maps instances of one problem to instances of another in pseudo-polynomial time, while keeping both the size of the instance and the magnitude of its largest number under polynomial control. If a strongly NP-complete problem has a pseudo-polynomial transformation to a problem in NP, then that second problem is also strongly NP-complete.
Definitions Maximal numerical parameter Some computational problems are parameterized by numbers whose magnitude exponentially exceeds the input size. For example, in the partition problem the input is a list of n positive integers, and the relevant numerical parameter is the largest of them. The problem can be solved by dynamic programming in time polynomial in n and the sum of the integers, which is exponential in the length of the binary encoding of the input, so the algorithm is pseudo-polynomial.
Let be a computational problem whose instances are encoded as strings over an alphabet . The function
maps , the encoding of an instance of , to the maximal numerical parameter of . It is assumed to be computable in polynomial time.
Pseudo-polynomial transformation Let and be decision problems, and let and be the languages of encodings of their yes-instances, over alphabets and respectively.
A pseudo-polynomial transformation from to is a function such that
can be computed in time polynomial in the two variables and
Intuitively: Condition (1) says that f preserves answers, so instances of can be decided by deciding their images under f (and back). Condition (2) says that the transformation is cheap: it runs in pseudo-polynomial time, and in particular the size of is bounded by a polynomial in and . Condition (4) says that the numbers in do not blow up. Together with (2), it ensures that deciding by applying f and then a pseudo-polynomial decider for is pseudo-polynomial itself. Condition (3) says that is not much shorter than w: the length of w is polynomially bounded in the length of . This allows bounds expressed in terms of to be re-expressed in terms of . Conditions (3) and (4) together ensure that a subproblem of witnessing strong NP-completeness (all instances have numerical parameters bounded by a polynomial in the input size, and the subproblem is itself NP-complete) is mapped into a subproblem of whose instances also have numerical parameters bounded by a polynomial in the input size.
Proving strong NP-completeness The following lemma allows to derive strong NP-completeness from the existence of a transformation:
If is a strongly NP-complete decision problem, is a decision problem in NP, and there exists a pseudo-polynomial transformation from to , then is strongly NP-complete
Proof of the lemma Let be a strongly NP-complete decision problem encoded by over , and let be a decision problem in NP encoded by over . Let be a pseudo-polynomial transformation from to , with and as in the definition.
By the definition of strong NP-completeness, there is a polynomial such that
is NP-complete. Define the polynomial . All of , and have coefficients in , so they are non-decreasing.
For any with ,
Hence, by condition 1, f maps such w to strings in
exactly when w is in . Moreover, when , condition 2 shows that is computable in time polynomial in .
Now define g by if (a polynomial-time check), and otherwise for a fixed string . Then g is a polynomial-time many-one reduction from to . Since is NP-complete, is NP-hard. It is also in NP, because is in NP and the bound can be checked in polynomial time. Therefore is NP-complete.
By the definition of strong NP-completeness, it follows that is strongly NP-complete.
See also Strong NP-completeness Pseudo-polynomial time Reduction (complexity) Partition problem
References