Facets of Reductions [cpsc/reduction-facets]

Reductions are helpful!

• Method: find a way to map:

  • yes-instances of $P_{1}$ to yes-instances of $P_{2}$
  • no-instances of $P_{1}$ to no-instances of $P_{2}$
• Notation: $P_{1}\underset{P}{\leq}P_{2}$
• Logic: if $P_{2}$ is easy, $P_{1}$ is easy
• Contrapositive: if $P_{1}$ is hard, $P_{2}$ is hard

Theorem.

If $A\underset{P}{\leq}B$ and $B \in P$, then $A \in P$.

• There is a polytime Turing machine N that decides $B$.
• There is a polytime reduction $f$ from $A$ to $B$.

Proof.

We want a Turing machine $M$ that decides $A$ in polynomial time.

• On input $x$: compute $z = f(x)$ and then simulate $N$ on input $z$. Accept iff $N$ accepts.
• If $x \in A\Rightarrow f(x) \in B\Rightarrow N\ \text{accepts}$.
• If $x \in A^{\_}\Rightarrow f(x) \notin B\Rightarrow N\ \text{rejects}$.

When we talked about Turing machines, we had a notion of what it meant to be hard: undecidability. But now we’re talking about NP. So which problems in NP are hard?

Maybe $\text{P} = \text{NP}$, and so all problems in NP are easy.