reduction

When talking about computer sciency problems -- the sort of problems that people like to call NP-complete and such -- people often say things like "problem A can be reduced to problem B".

The word reduce is confusing to me.

This "reduction" makes it sound like a large problem called A is becoming smaller -- reducing in size -- so it can fit somehow in B.

But that's wrong. B is generally a bigger and harder problem than A.

For example, we might "reduce" the problem of finding the maximum number in a set of numbers to the problem of sorting the numbers. That is, we can sort the numbers, and then we'll get the maximum number for free by looking at the last number in the sorting. But sorting is harder than finding the max, so we didn't really reduce the size of the problem of finding the maximum number when we sorted the numbers -- we did more work than we needed to.

So, I propose that we stop saying "reduce", and saying something like "embed" or "express in terms of".

I can embed the problem of finding the maximum number into the problem of sorting numbers, or I can express the problem of finding the maximum number in terms of the problem of sorting numbers.