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

- f is computable in polynomial time.
- For every
*x*, *x* ∈ *A* ⇔ f(*x*) ∈ *B*.

**Definition.**
Say that *A* ≤_{p} *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

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.