08 Polynomial-time reductions

A reduction, as in mathematics, is a way of saying that one problem is ‘as hard’ as another. For complexity theory, we require the reduction itself to be efficiently computed:

Definition

Fix languages $L,L^{\prime }\subseteq \{0,1{\}}^{\star }$. A polynomial-time reduction from $L$ to $L^{\prime }$ is a function $f:\{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$ such that:

• $f$ is polynomial-time, i.e., we can compute $f(x)$ in a number of steps polynomial in $|x|$.
• $x\in L⟺f(x)\in L^{\prime }$

We write $L{\le }_p{L}^{\prime }$ when there is a polynomial-time reduction from $L$ to $L^{\prime }$.

Example: Reducing Independent-Set to Clique

K-Independent Set = $\{(G,K):\exists I\subseteq G\text{ of size }\ge K(\forall u,v\in I\text{ distinct }u\ne v\text{ in G})\}$

Reduction from K-Independent to K-Clique

• Define: $f:(G,K)\mapsto (\bar{G},K)$ ($\bar{G}$ is like $G$, but flip all edges)
• $f$ is certainly polynomial time
• $(G,K)\leftarrow$ K-Independent Set
  • $\Rightarrow \exists$ C a k-Independent Set in G
  • $\Rightarrow \exists$ C a k-clique in $\bar{G}$
  • $\Rightarrow (\bar{G},K)\in$ k-clique
• $\Leftarrow$ (similar)