Polynomial Reduction

A (decision) problem A is polynomial time reducible to a decision problem B, if there is a polynomial time algorithm $F$ that transforms any instance $I_A$ of $A$ to an instance $I_B$ of $B$ such that

$I_A$ is a YES instance of $A$ $⟺$ $F(I_A)=I_B$ is a YES instance of $B$

Notation

• We write $A{\le }_{P}B$, if such a polynomial time reduction exists.
• We also write $A{=}_{P}B$ if $A{\le }_{P}B$ and $B{\le }_{P}A$.

• Informally: ”$B$ is at least as hard as $A$”. If I could solve $B$, I could solve $A$.

Lemma

$A{\le }_{P}B\text{ and }B{\le }_{P}C⟹A{\le }_{P}C$

Questions

I don’t understand this concept very well. I always think of $A{=}_{P}B$, because in the proof, you have $F(I_A)$.

• The best way to think about this is that you are going from a easier problem to a harder problem. Like using hamiltonian path to prove decision k-st, but you only look at the transformed instances from $I_A$?
  • like the problem space of $I_B$ is reduced
  • But the transformation does nothing in this case
• noo, i’m still confused
• Like $\text{subset sum}{=}_P\text{subset-sum one}$, its actually equivalent

Yea, I think I understand now. You just want to use your mapped values and prove that they work in the opposite direction. You are reducing the problem space.

• Yeaa, so you can create a function for example, that maps $F(G)=(G,2)$ for example in the hamiltonian path → decision k-st problem
  • Also a wikipedia that talks about this https://en.wikipedia.org/wiki/Degree-constrained_spanning_tree#:~:text=NP-completeness

Exercise

Assume $A$ and $B$ are decision problems and we are given:

• an algorithm $Al{g}_B$, which solves $B$ in polynomial time,
• a polynomial reduction $F$, which gives $A{\le }_{P}B$.

Design a polynomial time algorithm to solve $A$:

1. Use $F$ to transform $I_A$ to $I_B$
2. Return $Al{g}_B(I_B)$

Related

• Clique Problem