Proof

I have a friend who's written a chapter in a book that he says is aimed to the top 1% of math students. I wonder if that's like writing a book to the wealtiest 1%. Is that not limiting the audience a little too much?

And what exactly is this audience anyway? In effect, writing for such a group is a bit of a theoretical exercise. You have imagine what that 1% must be like, perhaps using yourself as a reference.

And there's that too. So, there's this math book that a bunch of grad students are writing, and surely, the conclusion is that it's written by bright folks for bright folks.

Now, I'm not saying it's a bad idea. I just think it may be challenging to write to a consistent level for different authors. A collection of articles written together doesn't usually produce a great result. Have you noticed most books are written by one or two people? That might be saying something.

So what's my point? Is it simply to rant? Not this time, at least, not for the rest of this post.

Which, if I may digress for just a minute, I should say that Blogger has done one thing wrong, which is that they display the entire contents of each entry. They should mimic a newspaper, and only show a few paragraphs.

I know, I know. Most people's entries are only a few paragraphs. But for people like me, there should be more posts, and the opening paragraphs should serve as teaser.

But back to the point.

I'm going to try to achieve the same goal as my friend by doing a tutorial on computational complexity. I don't plan to get very far, just enough to whet the appetite.

I'm just seeing where I go with this.

Here we go.

Suppose I give you two problems. For sake of example, I might give you two calculus problems. I ask you which problem is harder. How would you decide which problem is harder?

Maybe you work on one a few minutes, then work on the other a few minutes. Eventually, you might solve one first and declare that the easier problem.

But are you a good arbiter of what problems are hard or not? Is there a better way to tell which problems are hard or easy?

Maybe I can get a classroom of people to do those two problems and then take a poll. I could interview the folks and ask why they thought this problem was hard or that problem was hard.

To a mathematician, this would seem a horrible way to decide the difficulty of a problem. It lacks precision. It's based on people's opinions. Math, if nothing, teaches us to be precise, teaches us that if we phrase our problems precisely, we have a much better chance of solving the problem.

And usually the place a mathematician might start is with a good definition. What is a problem?

Mathematicians aren't interested in all problems. They have no answers to world peace, or the secrets of a good marriage. They want problems that can be stated and reasoned in a precise manner.

Let's start off with a problem. I give you a list of numbers, say, (10, 8, 2, 5). The problem is to rearrange these numbers in increasing order. This problem is often called sorting. The solution to this problem is (2, 5, 8, 10).

You can think of a problem as associating an "input", in this case, an arbitrary list of numbers, with the "output" or solution, in this case, a sorted list.

I suppose that's not the greatest definition of a problem, i.e., a mapping of an input to an output, but it's a start, right?

Now, how do we get from the input to the output? An algorithm is a recipe for coming up with an output, given an input. Most people care that the algorithm is "correct", i.e., that it comes up with the right answer. For example, if you have the list (10, 2, 5), you don't want the output to be (5, 2, 10) since that is not in increasing order.

To convince someone an algorithm is correct, you do what mathematicians do to convince each other they are correct. You bully others mercilessly and yell at them until they are scared into agreeing with you.

Just kidding. You prove to them that you are correct. You use rules of deduction that both of you accept are agreeable to convince someone of an argument.

Although algorithms are most often associated with a computer, there's no reason a computer has to do it. For example, if I have a list of names, and I want you to sort it in alphabetical order, I can give you several ways to do this. While I could write a program to do the same thing, I could have you do it too. Of course, you might not follow my directions exactly, a problem a computer program generally doesn't have.

Even so, let's imagine that I have two programs, both of which can sort a list of numbers. How can I tell which one is faster?

Your first inclination may be to run the programs and just time it. But, maybe you wrote your program on your snazzy 2 GHz machine, and I'm running on a 64 MHz clunker. Maybe you're a clever coder and know something about what assembly language instructions are faster on your machine, and I code in a dumb way for my machine.

People used to measure programs just like that. Basically taking a stopwatch. And yet, they were comparing apples to oranges. OK, so maybe we could make the challenge more even by writing on the same computer. And maybe in the same programming language.

But even then, maybe one of us knows something tricky about the language that allows one of us to do it faster, not for any fundamental reason for solving the problem, but due to something that these computers somehow to better, for no good reasons except they were designed this way.

There were two computer scientists, Robert Tarjan and John Hopcroft, both at Stanford at the time, nearly forty years ago, that thought measuring one program against another using this stopwatch technique was an awful way to compare two programs, i.e., two algorithms.

They wanted some way to compare two algorithms that made sense even if technology were to improve the speeds of computers, even if compilers were written better. They felt there must be some salient feature that they could measure that would not change even as computer speeds increased.

They decided that what was important was not how well an algorithm solved one particular problem, e.g., how well it solved, say, sorting (2, 10, 5), but instead, it would see how much more work it took to solve the problem as the size of the input increased.

So, (2, 10, 5) is a list of 3 numbers. What if you had 6 numbers? Would it take twice as long to sort it? Would it take more than twice as long? Would it take less? Forget, for a moment, how we decide whether it takes twice as long, or more, or less.

Just think about it. It doesn't matter now if we have a computer that runs twice as fast, because what we care about is a ratio. For example, it may take one minute to sort 3 numbers on a slow (really, really slow) machine, and take two minutes to sort 6 numbers.

And on a much faster machine, the difference might be 3 milliseconds to sort 3 numbers, versus 6 milliseconds to sort 6 numbers.

The hope is that if you use a faster computer with the same algorithm, the same basic shape of the plot between input size and time will hold. And people have shown that this does basically happen.

For sorting algorithms, we can measure something that should stay the same regardless of how often pairs of numbers. Most sorting algorithms require you to look at two numbers in the list, decide which is bigger, then move numbers around.

For example, if you have (10, 2, 5), then a typical sorting algorithm might start off comparing 10 to 2. The rule might be: if the first number is bigger than the second, exchange them. Thus, you see 10 is bigger than 2, so you exchange (2, 10, 5).

So one way you could measure how much work it takes to sort a list of numbers is to ask how often you must compare pairs of numbers.

The great news about that is that, again, it doesn't depend on how fast your computer is. A faster computer simply makes each comparison faster. It doesn't make fewer comparisons.

However, two algorithms might take different approaches to sorting, and you could compare how many comparisons both made. Of course, if one algorithm somehow avoids making any comparisons, then perhaps measuring comparisons is the wrong way to go.

Now, why should you care? Sorting is a very common operation in many programs. If you can find a good way to sort, you can run your programs more efficiently, and sometimes so efficiently that you can go home early from work.

Ah, but really, people realized that the more clever their algorithm was (i.e., the better their approach to solving problems), the happier everyone was.

But that begged the question. How do you compare two algorithms? Should you simply run it and count the steps?

To be continued...