|
A polynomial time reduction is a mapping reduction that can be computed in polynomial time.
Suppose that A and B are two languages.
Definition. Function f is a polynomial-time reduction from A to B if both of the following are true.
Definition. Say that A ≤p B if there exists a polynomial-time reduction from A to B.
Most of the reductions that we did while looking at computability are polynomial time reductions.
We saw the trivial reduction f(x) = x + 1 from the set of even integers to the set of odd integers. That is a polynomial time reduction because
There is an algorithm that adds 1 to an n-digit number in time O(n).
For every integer x, x is even ⇔ x+1 is odd.
|