# 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≤_{P}B$, if such a polynomial time reduction exists.
- We also write $A=_{P}B$ if $A≤_{P}B$ and $B≤_{P}A$.

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

Lemma

$A≤_{P}BandB≤_{P}C⟹A≤_{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 $subset sum=_{P}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 $Alg_{B}$, which solves $B$ in polynomial time,
- a polynomial reduction $F$, which gives $A≤_{P}B$.

Design a polynomial time algorithm to solve $A$:

- Use $F$ to transform $I_{A}$ to $I_{B}$
- Return $Alg_{B}(I_{B})$