Reductions

This lesson is optional.

In complexity theory, the concept of reductions is fundamental for comparing the complexity of different problems. A reduction is a way of transforming one problem into another in such a manner that a solution to the second problem can be used to solve the first problem. This concept is used to show that one problem is at least as hard as another.

To see an example of a reduction, watch the following video: