Reducibility

Before we proceed on to defining the NP-HARD and NP-COMPLETE classes, it is important to look at the idea of reducibility. Reducibility means that one problem can be restated in terms of another. For instance, consider the trivial example of finding the median of a set of numbers. If we were to design an algorithm to do this, the first step would be to sort the list of numbers, then we would pick out the number right in the middle. So, we say that the problem of finding the median is reducible to the problem of sorting a list of numbers, because sorting solves our problem of finding the median.

Reducibility is often a misnomer. Reducing problem $\Phi_1$ to $\Phi_2$ often means that $\Phi_2$ is harder. This is not a reduction at all. Notationally, we say that $\Phi_1 \leq \Phi_2$.

Nevertheless, we are interested in P-time reducibility. We say that a problem $\Phi_1$ is P-time reducible to $\Phi_2$ if there exists a function $f$ in $P$ such that $\Phi_1(i) \leq \Phi_2 (f(i))$.