![]() | This article has multiple issues. Please help
improve it or discuss these issues on the
talk page. (
Learn how and when to remove these template messages)
|
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]
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 .
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
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.
The following lemma allows to derive strong NP-completeness from existence of a transformation:
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.
![]() | This article has multiple issues. Please help
improve it or discuss these issues on the
talk page. (
Learn how and when to remove these template messages)
|
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]
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 .
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
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.
The following lemma allows to derive strong NP-completeness from existence of a transformation:
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.