The Math Less Traveled

As promised (better late than never), I’m going to begin explaining the (in)famous P vs NP question (see the previous post for a bit more context). As a start, here’s a super-concise, 30,000-foot version of the question:

Are there problems whose solutions can be efficiently verified, but which cannot be efficiently solved?

Of course, this is so vague as to be almost meaningless! My job over the next few posts will be to un-vagueify it for you. Looking at the statement, three questions may immediately come to mind, and we’ll consider each in turn:

• What counts as a problem?
• What do we mean by efficient?
• What do we mean by verify?

Today we’ll start by considering the first question: what counts as a problem?

The P vs NP question is usually stated in terms of decision problems, which are problems with a yes/no answer. For example, Is there a way to drive from here to Kalamazoo without driving on a major highway? Either there is a way to do it, or there isn’t, and we might hope that a computer (given an appropriate map as input) would be able to tell us which.

Of course, not every problem is a decision problem. For example, How long does it take to get to Kalamazoo if you go by the fastest possible route? We might hope that a computer could answer this question too, but the answer we are looking for is an amount of time, rather than yes or no. This is not an isolated example; there are lots of interesting and important problems like this. So why restrict ourselves to just decision problems?

It’s easy to see that decision problems are the simplest possible kind of problem. The answer carries just a single “bit” of information. (The only thing that could possibly be simpler than a problem with a yes/no answer is a problem with a “no/no” answer, which carries zero information. For example, “Does this dress make me look fat?” But these aren’t the sorts of problems we are usually interested in solving with a computer.) There is a long scientific tradition of studying the simplest possible kind of something, in order to gain insight into more complicated things as well. That’s what we’re doing here.

But can studying decision problems really give us insight into problems with more complicated answers as well? Actually, yes! To see an example of what I mean, consider again our question How long does it take to get to Kalamazoo if you go by the fastest possible route? This is a problem with a “complicated” answer (you might think that a single number is not very complicated, but you have to admit that it is way more complicated than a simple yes/no!). But now consider this related question: Is it possible to get to Kalamazoo in minutes or fewer? Actually, this is a whole family of questions parameterized by the time . For any particular , this is clearly a decision problem with a yes or no answer. But if we had a computer program which could efficiently solve this problem for any , we could use it to solve the original problem to any desired accuracy. For example, we might ask the following series questions, with the answer to each question shown in bold:

• Is it possible to get to Kalamazoo in 1000 minutes or fewer? YES
• Is it possible to get to Kalamazoo in 500 minutes or fewer? NO
• Is it possible to get to Kalamazoo in 750 minutes or fewer? YES
• Is it possible to get to Kalamazoo in 625 minutes or fewer? NO
• and so on…

After only a few more questions, we would learn that if we go by the fastest possible route and go exactly the speed limit the whole time and never stop for food or gas or to use a restroom, it would take exactly 665 minutes to get to Kalamazoo.

“That’s all very well,” you might say, “I can see how that works for problems with numerical answers. But what about answers that are more complicated yet?” For example, what if we wanted to know not only the time it takes to get to Kalamazoo by the fastest route, but also the route itself? This is certainly not just a number, it is a list of turns, or a list of street names, or something complicated like that. Surely we can’t reduce this to just some decision problem?

Well, no matter how complicated the answer to a problem, it is always possible to encode the answer in binary, as a sequence of ones and zeros. For example, to encode a series of turns we might agree to encode a left turn as 01, a right turn as 10, going straight as 11, and use 00 to indicate the end of the directions. So 011110101100 would mean “Turn left, then go straight, then turn left twice, go straight again, and you’re there.” In order to encode street names we would need a much more complex encoding but it can be done easily enough. For example we might encode the letter A as 00000, B as 00001, C as 00010, and so on.

OK, so what? Here’s the punchline: given a problem P with some complicated answer and a suitable way to encode the answer to P in binary, we can make the following decision problem:

Is the th binary digit in the binary encoding of the answer to P a one?

I hope you can see how we could use a computer program capable of solving this problem for any to solve the original problem: just ask about the binary digit (or bit) at each position, and build up the answer to P one bit at a time.

Perhaps you think this is bit contrived. But it shows that in some sense, there’s nothing fundamentally interesting going on with problems that have complicated answers; we can always reduce them to decision problems. So for these reasons (and perhaps a few others), the P vs NP question is phrased in terms of decision problems only. We can now restate the P vs NP question a bit more precisely:

Are there decision problems whose solutions can be efficiently verified, but which cannot be efficiently solved?

In my next post, I’ll explain what we mean by that hand-wavy word efficiently.