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


  • 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 .



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.


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