On reduction

I have a legitimate excuse for being an absent blogfather, I swear. It involves most recently a five-day mathematics conference, and before that at least a week of putting off writing my slides.

In honor of this excuse, however, I think I'll do a post, or maybe more, on some of the ideas that I have bouncing around now. In particular, I'd like to say enough that a dedicated reader (of which I have, I think, precisely zero) could follow two proofs that I really should have known coming into the conference -- though I really can't blame myself, since as far as I know they both only appear in the literature in far more complicated form. Until now, nobody bothered to say "Oh, what's actually going on here is not that complicated, here's the paradigmatic example". Something like Feynmann's hairy handlebodies.

This is, I suppose, what conferences are for: getting free use of a lot of people's bounce-off-the-wall capabilities.

But before I can do that, I have to say a little bit about the mathematical tool being used. Tool? Tools? Eh, who cares. There's one main tool, and one smaller one that is really just a very, very helpful definition; then lastly we'll build a special version of the first tool.


There's an old joke I like to tell.

A professor walks into her classroom -- a large lecture hall in the science building -- the first day of freshman calculus. Now, the course is designed to be for students in technical majors, but many of the students have not decided whether to pursue engineering, or physics, or chemistry, or math, or whatever. So the professor opens up her first day of class by telling the students, "I am going to help you decide whether you have the right temperament for majoring in math, or in physics, or in engineering." The students look skeptical, but curious.
The professor cleared of the metal counter at the front of the room, which had a sink and bunsen burner at each end. Then she took out a sheet of paper and an empty glass beaker, brought them to one end of the counter, and lit the paper on fire with the burner. "Oh goodness!" she shouted. "There's a fire, what do we do?" One student replied: "Fill up the beaker in the sink and pour it on the burning paper." Which she did.
"Thank you, Mr..." She paused while scanning her roster photos "... Saunders. You, I think, have what it takes to be a physicist: you took an unexpected situation that, I would guess, you haven't encountered before, found general-purpose resources and used them to solve this specific problem."
But the professor was not finished with the sorting. She found another sheet of paper and another beaker, brought them to the other end of the counter, and lit this paper on fire too. "Oh no, a fire!" she intoned. "What should we do?" Two students in the front row looked at each other, then at the fire, and then said almost in unison, "Fill the beaker with water from the sink and pour it on the paper?"
"Ms... Gomez and Ms..." the professor scanned the sheet as she poured, "van Eyeck have, I think, admirably demonstrated the temperament of a successful engineer: know what problems have been solved in the past, and change only those details needed to solve the current one." With the flames safely out, the professor dried her hands and said "Well then, on to calculus."
"Excuse me, professor," interrupted van Eyeck, "but do you expect any math majors from this class then?" "I wouldn't rule it out," said the professor, "but in my experience a mathematician's response to the second fire would be to pick up the burning paper with his or her bare hands, carry it to the first sink, and then exclaim triumphantly that we've reduced the situation to a solved problem and are therefore done."

The moral of the story really isn't that asbestos hands should be a job requirement for mathematicians, of course, but that frequently the key to solving a mathematical problem is finding out how to twist it around (without compromising any of the important features) until it looks like something you're more familiar with.

So far, so vague, right? Let's look at one form this takes.

In computer science, "problem" sometimes has a specialized meaning:

Given a (finite) alphabet \(A\) of symbols, a problem is a subset \(P\) of the set \(A*\) of all strings whose letters come from \(A\). We are supposed to imagine how we might answer the question, preferably using an algorithm, of answering "yes" or "no" to the question "Does string \(s\) belong to \(P\)?

These are sometimes called "decision problems" to emphasize their two main features: first, the only possible answers to the question are "yes" and "no" (you could also specify "true" and "false" if you felt like it), rather than returning some more complicated object (like an integer or another string); second, they involve sets considered as subsets of some fixed universe (in this case, the universe is the set of all possible strings in that alphabet). For example, say \( A \) is the digits 0-9, and \(P\) is the set of all strings containing the digits 1-9 which code a valid Sudoku square. (So the first row is given by the first nine digits, the second row by the next nine, etc.)

This \(P\), naturally, isn't that difficult a problem to decide. (Though actually coding it into a computer would be something of a pain: First check if any of the digits is zero; if yes, return "no". Then check if the length of the string is 81; if no, return "no". Then check if each digit occurs exactly once in positions 1-9. If no, return "no". Then check all the other rows and columns and  \( 3 \times 3 \) squares in the same way. If you make it through all 27, return "yes".)

When this is our meaning of "problem", the most common meaning of "reduction" is this:
Say \(P\) and \(Q\) are problems over alphabets \(A\) and \(B\) respectively. A reduction of \(P\) to \(Q\) is a function \(f\) which

• takes \(A\)-strings as input,
• gives \(B\)-strings as output, and
• has the property that \(s\) belongs to \(P\) if and only if \(f(s)\) belongs to \(Q\).

Well, if we're going to call this a "reduction", it probably ought to comport with the informal meaning we were using above. Does it? Suppose we have a doctor on staff -- call him Dr. House -- who knows everything about problem Q. If you give him any string in \(B^*\), he'll tell you whether it's in \(Q\) or not. Dr. House has solved problem \(Q\), basically. But now, if you want to solve problem \(P\) -- that is, if you have some \(s\) in \(A^*\) and you want to know if \(s\) belongs to \(P\), here's your plan: you compute \(f(s)\). Then you ask Dr. House if \(f(s)\) belongs to \(Q\). After calling you abusive and very funny names for a few minutes, House tells you that, yes, \(f(s)\) belongs to \(Q\) (or maybe he tells you that it doesn't). But remember: you already know that \(f(s)\) belongs to \(Q\) iff \(s\) belongs to \(P\). Hooray, you're done! And you leave the calculus classroom as the flames jump from the paper to other inflammable objects.

Ok, so maybe we should get a few more miles out of our Sudoku example. Let \(Q\) be the set of strings we considered before, the ones which code complete and valid sudokus (with all spaces filled in). Let \(P\) be the set of all strings of length 81 in the alphabet 0-9 (where "0" means "blank square") that have exactly one correct solution as a sudoku puzzle. (If the guy or gal who supplies sudoku puzzles to your daily paper is good at their job, then every puzzle they provide belongs to \(P\).)

What's the first thing we notice about this? Well, firstly, \(Q\) is a (relatively) easy problem; \(P\) is not! But they clearly have a relationship. (This will not always be so obvious!)

The second thing we notice is that \( Q \subset P \). Every complete sudoku configuration has just one completion -- itself! But \(P\) is much bigger than \(Q\).

So now I'm going to do a little magic: I'm going to define a function, but not tell you how to compute it. I realize that this feels kind of like cheating, and in the next couple of posts, when I'm actually building useful reductions, I'll show you how to compute the reduction function. But it's useful as a teaching tool, because the way to think about problem reduction is to only look at one thing at a time, and to treat everything else as magic -- we actually call everything else a black box that we don't have to know the internal workings of.

So here goes: if \(s\) is a string in the alphabet 0-9, and \( |s| \neq 81 \), then \(f(s) = s \). Otherwise, if \(s\) has the right length, then we form \(f(s)\) by replacing every 0 digit in \(s\) with the least nonzero digit which the other information in the puzzle implies, if any such implication exists.

So yes: cheating. Looking for implications is really, really hard! But whether or not you believe me that you can actually write down an algorithm which computes this function (it's true, you can), I think everyone will agree that

• if \(s\) has contradictory information, then \(f(s)\) may have digits in all the spots, but it will definitely not be a valid sudoku;
• if \(s\) has multiple possible completions, then \(f(s)\) will have 0 digits; and
• if \(s\) has exactly one completion, then \(f(s)\) will be that valid, complete sudoku configuration.

In other words, \(f\) is a reduction function from \(P\) to \(Q\): \(s \in P \) if and only if \(f(s) \in Q\).

It's this kind of "reduction" that computer scientists mean when they say that every polynomial-time problem "reduces to" the Traveling Salesman Problem, for example. But looking back at the joke about the calc students, it really doesn't seem like this definition matches what the professor says mathematicians do.

So we need a more general definition. But I'll hold off on introducing that until we need it.