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'\) is at least as expressive of \(L\) if \(L\) can be reduced to \(L'\).