# Polynomial Reduction

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

is a YES instance of is a YES instance of

Notation

• We write , if such a polynomial time reduction exists.
• We also write if and .
• Informally: ” is at least as hard as ”. If I could solve , I could solve .

Lemma

### Questions

I don’t understand this concept very well. I always think of , because in the proof, you have .

• 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 ?
• like the problem space of is reduced
• But the transformation does nothing in this case
• noo, i’m still confused
• Like , 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.

### Exercise

Assume and are decision problems and we are given:

• an algorithm , which solves in polynomial time,
• a polynomial reduction , which gives .

Design a polynomial time algorithm to solve :

1. Use to transform to
2. Return