Poly-Time Reductions

Problem $X$ polynomial-time reduces to problem $Y$ ($X{\le }_{p}Y$) if arbitray instances of problem $X$ can be solved using

1. Polynomial number of standard computational steps, and
2. Polynomial number of calls to oracle that solves problem $Y$.

Prove $X{\le }_{p}Y$

1. Construct problem Y by using problem X
2. Verify contruction is correct. $X\to Y$ and $Y\to X$
3. Verify there’s polynomial times contruction and calls.
4. Done

Known reductions

1. SAT Problem ${\le }_P$ 3-SAT Problem ${\le }_P$ Independent Set Problem ${\le }_P$ Vertex Cover Problem ${\le }_P$ Set Cover Problem

2. 3-SAT Problem ${\le }_P$ Subset Sum Problem

3. Subset Sum Problem ${\le }_P$ Knapsack Problem

4. Subset Sum Problem ${\le }_P$ Partition Problem

5. Partition Problem ${\le }_P$ Subset Sum Problem

6. Hamiltonian Cycle ${\le }_P$ TSP