Reduction

When discussing a complexity class $C$, we say that a problem $P$ is $C$-complete, if for every problem $A$ in $C$, $A$ can be reduced to $P$.

Here, 'reducing' $A$ to $P$ means that we can phrase the problem of solving $A$ in terms of solving $P$. If $A$ can be reduced to $P$, then we say that $P$ is at least as hard as $A$. After all, if $A$ can be reduced to $P$, then any solution to $P$ would give a solution to $A$.

Some things to remember:

• When proving NP-completeness, we're usually reducing 3-SAT to some problem $P$, because 3-SAT has already been shown to be NP-complete
• We're reducing to the problem that we want to show is (at least) harder. This sounds a little funny, since we might expect that big things are reduced to small things. For me, it's easier to replace the word "reducing" with the phrase "representing $A$ using $P$'s symbols".

A language $L^{\prime }$ is at least as expressive of $L$ if $L$ can be reduced to $L^{\prime }$.