Flight Lab / Graduate algorithms / 04

Lesson 04 of 05 · about 5 min

Point the reduction

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5

A reduction turns an instance of one problem into an instance of another, in polynomial time. To show a problem is hard, reduce a problem you already know is hard into it. A reduction the other way, into an easy problem, would show it is easy.

Bin packing is the problem on trial. 3-SAT is NP-complete. Sorting is polynomial. Pick the reduction that shows bin packing is hard.

On the Knowledge page

Resources