# A Simple Definition

The formal definition of “NP-Complete” uses reductions, or transformations, of one problem to another. Suppose we want to solve a problem P and we already have an algorithm for another problem Q. Suppose we also have a function T that takes an input x for P and produces T(x), an input for Q such that the correct answer for P on x is yes if and only if the correct answer for Q on T(x) is yes. Then, by composing T and the algorithm for Q, we have an algorithm for P.

Simple. Right?

If you enjoyed this post, please subscribe.