Definition. polytime reduction [polytime-reduction]

Let A,B⊆Σ*A,B \subseteq \Sigma \ast (A,BA,B are languages). ff is a polytime reduction from AA to BB if:

  1. ff is a Polytime computable function
  • x∈A⇒f(x)∈B(f(A)⊆B)x \in A\Rightarrow f(x) \in B\left( {f(A) \subseteq B} \right)
  • x∉B⇒f(x)∉B(f(A−⊆B−))x \notin B\Rightarrow f(x) \notin B\left( {f\left( {A^{-} \subseteq B^{-}} \right)} \right)

We then may say A≤PBA\underset{P}{\leq}B.

Example.

Suppose A={0n10n:n≥0}A = \left\{ {0^{n}10^{n}:n \geq 0} \right\}, and B={1n01n:n≥0}B = \left\{ {1^{n}01^{n}:n \geq 0} \right\}. Claim: A≤PBA\underset{P}{\leq}B

What does this mean? It means there exists some function that can take a String, map it, and manipulate it so that if x∈Ax \in A, then x∈Bx \in B, and the same for converses.

Proof:

  1. Let ff be the function that flips bits of its input. ◼\blacksquare

    • x∈A⇒f(x)∈Bx \in A\Rightarrow f(x) \in B
    • x∉A⇒f(x)∉Bx \notin A\Rightarrow f(x) \notin B
    • f(x)∈B⇒x∈Af(x) \in B\Rightarrow x \in A
    • x∈A⇔f(x)∈Bx \in A\Leftrightarrow f(x) \in B

Note that these do not need to be bijections! A reduction that simply sends all satisfiable inputs to 00 is fine.