10.1. Polynomial-Time Reductions and Reducibility

Polynomial-time reductions

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.

  1. f is computable in polynomial time.
  2. For every x, xA ⇔ f(x) ∈ B.

Definition. Say that Ap B if there exists a polynomial-time reduction from A to B.

An example

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

  1. There is an algorithm that adds 1 to an n-digit number in time O(n).

  2. For every integer x, x is even ⇔ x+1 is odd.