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.

The million dollar question: why the excitement? Well, that’s exactly it: it is a million-dollar question. The P vs NP problem is one of the seven Millenium Prize Problems established in 2000 by the Clay Mathematics Institute; each problem carries with it a prize of $1,000,000. One of the seven — the Poincaré Conjecture — has already been solved, by the Russian mathematician Grigori Perelman (who famously refused to accept both a Fields Medal and the $1 million). And it’s not even really about the $1 million prize; the P vs NP problem is widely agreed to be the most significant (and difficult) open question in theoretical computer science, so for someone to solve it would be a Really Big Deal.

So, did Deolalikar really solve it? Will he win the $1 million? Well… it’s way too early to tell! Here are a few things to keep in mind:

• Since P vs NP is such a famous problem, there are tons of “attempts” at solving it published all the time. Most are by people who either have an overinflated estimate of their mathematical understanding, or believe the solution was told to them in a dream by benevolent aliens, or both. Hence they aren’t even really worth serious mathematicians’ time to read. Sad but true. But this is clearly not the case here: Deolalikar is a respected researcher who has done related work in the past, and his 100-page paper is well-written and demonstrates a good understanding of the relevant issues (you don’t have to take my word for it). Even if the proof ends up having some sort of fatal flaw, it’s clear that he has some interesting new ideas that may lead to other discoveries. Hence the excitement.
• Unfortunately, there have already been some possible flaws pointed out. But keep in mind that any paper of this magnitude is bound to contain tons of errors, omissions, and typos (if you don’t believe me, try writing one sometime!). Only time will tell whether these flaws turn out to be fatal problems that invalidate Deolalikar’s entire approach, mistakes that can be fixed relatively easily, or just misunderstandings on the part of the people who pointed them out.
• Supposing the flaws are fixable and Deolalikar’s proof ends up being accepted by the mathematical community, it will still be quite a few years before he could possibly win the $1 million. First, the proof needs to be published in a major mathematical journal (which will probably take at least a year), then there is a mandatory two-year waiting period, and then a special committee has to examine the proof and decide whether to award the prize! So don’t hold your breath.

At this point, you may also be wondering what the heck the P vs NP problem actually is, and why it is so important. Fortunately, it’s the one Millenium Prize problem that I am actually qualified to explain, and in the following post or two I intend to do just that! (Unfortunately I am emphatically not qualified to explain anything about Deolalikar’s attempted proof.) I’ve been intending for quite a while to write about some interesting topics in the intersection of mathematics and computer science (my day job, after all, is as a computer scientist!) and this will provide the perfect excuse.

Imagine that instead of ten cookies and five students, you have fifty cookies and ten students. (It’s easier to quantify this situation using larger numbers.) How many ways can you distribute these cookies among the students so that no student has any more than ten cookies?

Students may be given any number of cookies less than or equal to ten, including zero. The cookies are identical, just as in the original problem, so, as with the original problem, it doesn’t matter which cookie the student gets, just how many. But the students, again, are *not* identical, so which student gets a specific number of cookies is important.

I unfortunately haven’t had much time to think about it yet. Feel free to leave comments, thoughts, partial solutions, and solutions in the comments!

Here’s a recent xkcd which as a math educator I found particularly funny. Some questions for my readers:

1. What numbers besides 3 and 9 would “work” here?
2. Do you have any particularly funny or interesting stories of students getting something right for the wrong reason? Post them in a comment (or, better yet, on your own blog if you have one!).

Also, many parts of my optimal change-carrying challenge remain unanswered (although this is likely due in part to the unfortunate downtime I experienced shortly after publishing it). If you haven’t already, give it a try, you’re sure to find some aspect of the problem that interests you!

I’ve been trying to optimize my change-carrying habits. What is the smallest amount of quarters, dimes, nickels and pennies one can carry while still being able to give perfect change (two decimals)?

It’s not 100% clear what Michael meant by “give perfect change”, but let’s assume the goal is to be able to make any amount between 1 and 99 cents. For non-US readers, US coins are worth 1, 5, 10, and 25 cents.

Some questions for exploration:

1. What’s the smallest number of coins you can come up with that works? What are they?
2. Are there multiple solutions, or is the solution unique?
3. How can you prove that a proposed solution is optimal? Unique?
4. Can you answer the question for a different system of coins? For example, I am currently spending the summer in Cambridge, England, where coins are worth 1, 2, 5, 10, 20, and 50 pence. What if you also include the 1- and 2-pound (100 and 200 pence) coins, and want to be able to make change for every amount up to 5 pounds (the smallest note)?
5. The US and UK coin systems both have the property that a greedy strategy works for giving the smallest amount of change. That is, to make a certain amount of change with the smallest possible number of coins, you can just keep picking the biggest coin less than or equal to the remaining amount. What about coin systems without this property? Do they make this problem harder? Easier?
6. If you got to design your own system of coins with whatever denominations you wanted, how would you design it so that the minimum number of coins needed to make all amounts between 1 and 99 cents is as small as possible? As LARGE as possible?
7. What are some methodologies for attacking this sort of question in general?

Feel free to come up with your own generalizations as well. Post questions, discussion, and solutions in the comments but don’t peek until you’ve tried solving it! I’ve posted another change-making puzzle before as well; the discussion there might also give you ideas.

I thought I’d take a post just to summarize some of the responses and solutions to the broken weight problem. As many commenters realized, the solution is that the weights are of sizes 1, 3, 9, and 27. Hmm, powers of three… coincidence? Of course not!

As several commenters noted, something involving base three readily presents itself if we realize that there are three possibilities for each weight: it can be on the left of the balance scale, on the right, or not on the scale at all. Since one side of the scale corresponds to adding the weight and the other side to subtracting, we are essentially writing numbers in base three, but using the digits -1, 0, and 1 instead of the usual 0, 1, 2. For example, 25 can be written as 10(-1)1, that is, (if we were really going to use this system we’d want to come up with a better symbol for -1). In fact, this is known as balanced ternary, and it is a fact (as proved by a few commenters) that n digits of balanced ternary allow us to uniquely represent every integer between . With four digits (as in the problem) we can uniquely represent every integer between -40 and 40. There was a bit of confusion in the comments about being able to represent some integers in more than one way, but I think if you try it out you will find that this is not the case.

From this problem (generalizing it to arbitrary numbers of weights), we can see that

JM noted that this generalizes to

and wondered whether this has anything to do with solving the problem, or with problems like it. Indeed it does; here’s one for you: suppose you are tasked with designing a set of weights. The weights should make it possible to weigh as many different integer weights as possible, without leaving any out, just like the weights 1, 3, 9, 27 make it possible to weigh every integer weight up to 40 without leaving any out. The one difference is that you want to have two identical copies of each weight. What is the best you can do?

I’ve left the problem slightly vague on purpose, but I hope you will have fun solving it and figuring out what it has to do with JM’s observation! Can you come up with other interesting generalizations of the problem?

Finally, Sam Shah posted a link to a description of his experience using the problem in a real-life problem-solving session.

A merchant had a forty pound measuring weight that broke into four pieces as the result of a fall. When the pieces were subsequently weighed, it was found that the weight of each piece was a whole number of pounds and that the four pieces could be used to weigh every integral weight between 1 and 40 pounds. What were the weights of the pieces?

Note that since this was a 17th-century merchant, he of course used a balance scale to weigh things. So, for example, he could use a 1-pound weight and a 4-pound weight to weigh a 3-pound object, by placing the 3-pound object and 1-pound weight on one side of the scale, and the 4-pound weight on the other side.

The solution to this puzzle is really fascinating and leads into all sorts of fun generalizations and other topics; I’ll write more later. For now, as always, feel free to leave questions, observations, and solutions in the comments (so don’t look at the comments before you’ve solved it if you don’t want to see the answer!).

Pretty much on their own, they figured out how to draw a map with four countries all touching each other, which therefore required four colors. When I challenged them to draw a map with five countries all touching each other, they came up with maps involving countries touching at a corner, and with “satellite” disconnected regions that had to be given the same color as the “mother country”. They also figured out that if we allow these things, we can draw maps requiring an arbitrary number of colors, and conjectured that without these things we can’t have five countries all touching each other. I then told them about the four-color theorem and we had fun trying to four-color a map of North America (including the US states).

Then I showed them how to interpret maps as graphs, why maps correspond to planar graphs, and how to turn the map-coloring question into a graph-coloring question. I showed them the complete graph on 5 vertices and how it would correspond to having five countries all touching each other. Then for fun I posed the three utilities problem, which after playing with for a while, they correctly guessed could not be solved within the given constraints. One student did come up with an ingenious solution involving a pair of “teleporters”, which (although I didn’t point this out to them at the time) corresponds to the fact that can be embedded on a torus! I then showed them how to interpret this also as a statement about graphs (specifically, the non-planarity of ), and then told them Kuratowski’s Theorem (which I still find rather amazing and magical).

To finish up, I had them explore the idea of dividing up a continent into countries only by drawing straight lines that went completely from one side of the continent to the other. They correctly figured out that such maps would always be two-colorable. We looked at some examples and their corresponding graphs (which, they noted, always consist of a bunch of quadrilaterals). When I showed them the inductive proof of two-colorability, one of the students noted that the proof generalized to non-straight boundaries, as long as the boundaries are drawn as continuous lines with both endpoints on the “coastline” of the continent (which I hadn’t realized)!

All in all, this was probably our most fun and engaging meeting yet! Now that the Mathcounts competition is over, I think we’ll have a lot of fun doing some more open-ended, exploratory things like this rather than practicing with problem sets.