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.[1]

Definitions

edit

Maximal numerical parameter

edit

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   in   divisions, therefore exponentially more than the input size  . Suppose that   is an encoding of a computational problem   over alphabet  , then

 

is a function that maps  , being the encoding of an instance   of the problem  , to the maximal numerical parameter of  .

Pseudo-polynomial transformation

edit

Suppose that   and   are decision problems,   and   are their encodings over correspondingly   and   alphabets.

A pseudo-polynomial transformation from   to   is a function   such that

  1.  
  2.   can be computed in time polynomial in two variables   and  
  3.  
  4.  

Intuitively, (1) allows one to reason about instances of   in terms of instances of   (and back), (2) ensures that deciding   using the transformation and a pseudo-polynomial decider for   is pseudo-polynomial itself, (3) enforces that   grows fast enough so that   must have a pseudo-polynomial decider, and (4) enforces that a subproblem of   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   whose instances also have numerical parameters bounded by a polynomial in input size.

Proving strong NP-completeness

edit

The following lemma allows to derive strong NP-completeness from 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

edit

Suppose that   is a strongly NP-complete decision problem encoded by   over   alphabet and   is a decision problem in NP encoded by   over   alphabet.

Let   be a pseudo-polynomial transformation from   to   with  ,   as specified in the definition.

From the definition of strong NP-completeness there exists a polynomial   such that   is NP-complete.

For   and any   there is

 

Therefore,

 

Since   is NP-complete and   is computable in polynomial time,   is NP-complete.

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

References

edit
  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.