# "Reducing" problems

In algorithms class, when talking about computational complexity and stuff like (whether) “P = NP”, at some point, the lecturer must have mentioned something like this:

We say a problem can be “reduced” to another iff any instance of the problem can be formulated as an instance of the other. In other words, the given problem can be thought of as a special case of the other problem.

Ok, it all sounds good and well. Until he/she mentions:

For example, the problem of solving single-variable degree-one polynomial equations can be reduced to the problem of solving single-variable degree-

twopolynomial equations. E.g.,`2x + 5 = 0`

can be thought of as a special-case of an equation of the form

`ax^2 + bx + c = 0`

where a = 0.

Well, when I first came across the idea of “reducing” problems, it doesn’t occur to me to be too weird to do such thing as “formulating a problem in terms of another” — because afterall, wasn’t that exactly how mathematicians solve problems?

What I *did* get really confused about, was *which direction is the phrase used
in?* Do we say “the degree-two problem reduced to the degree-one one”, or do we
say “the degree-one reduced to the degree-two one”? More importantly, how
could/should I *remember* which direction it goes?

# “Reduce”?

Of course then, the point here is — which the guy (/u/menuitem) in the thread
already pointed out — that using the phrase “reduce” seems a bit misleading.
Why “reduce”? Does it mean “if we reduce a problem, it somehow gets *simpler*,
in terms of the effort required to solve it”? — because taken at face value,
perhaps that’s what the phrase “to reduce a problem” might mean.

But on the other hand, being ones who *actually understand* what the phrase
means (since we read and understood its definition, right?), we can see that the
above, face-valued interpretation is actually giving exactly the opposite of the
correct interpretation. The problem with questions with exactly two answers, is
that if you get it wrong, you get it *completely* wrong, by getting the *exact
opposite*. Meaning the exact opposite of what you *thought* you meant, well, may
be unhelpful.

We can see that the `ax^2 + bx + c = 0`

problem, which the arguably “simpler”
`ax + b = 0`

can be reduced to, is arguably “more difficult to solve”. Indeed,
there are kids who know how to solve the degree-one case but not the degree-two
case. In other words, after “reducing” a problem (to a new one), we’ve somehow
ended up with a more difficult problem than what we started off with.

Back in the “P = NP” (and of course, “NPC”) context, such apparently counterintuitive naming (to say the least) should be even more obvious — NPC problems are surely difficult to solve (i.e. efficiently), but people reduce lots of simple-looking problems to known NPC problems, and say “well if you want to solve this simple-looking problem (again, i.e. efficiently), you could first try solving any of this pile of really hard NPC problems”. Wouldn’t it seem weird that we say we’re “reducing” problems, but we’re ending up with the pile of hard NPC problems after doing the “reduction”?

So what exactly is being “reduced”?

# Reduce.

So, here you go — this is my way of interpreting and remembering which direction “reduce” means:

perhaps what’s being (literally speaking) reduced, is “the number of problems we need to care about how to solve”.

If we knew how to solve (i.e. in the sense of “having an algorithm for” or
“having a general formula for”) *any* (single-variable) polynomial equation,
then we wouldn’t care so much about how to solve say, 7th-order polynomial
equations, because they would merely be a special case which the formula can
handle. And I think we can all agree that this is nice. Such an act of
“summarising solutions into a general form” is a way to save dull-work, avoid
mistakes, and focus our attention on higher-level (i.e. “of abstraction”)
things.

In a software engineering point of view, I’d also say that it’s one of the
motivations of writing reusable code — each problem should be solve exactly
once; write once, use everywhere. If you haven’t noticed, the idea of “reducing”
a problem is nicely analogous to the idea of “making a call into a library
function”. You can find the minimal element in a list by calling some library
function `sort`

to sort your list and then taking the first element — that
way, you would have reduced “finding the minimal element” into “sorting the
list” by calling the `sort`

function. (Let’s focus on “reduction” instead of
“efficiency” here!) (Also, BTW, notice how “sorting a list” is a more
difficult-seeming problem than “finding the min” is.) I guess I’ve given a
not-really-good example here; but the idea is that you can write e.g. functions
that are, in some way, very general, so that it can handle various use-cases.