What is this “Computational Complexity”
Last month I mentioned that I was helping teach CS 159, a class entitled “Introduction to Computational Complexity”. I also mentioned that my interest in this subject is one of the main reason I ended up majoring in computer science. I didn’t, however, get a chance to explain what computational complexity is. Now that the class is over, I thought I’d write a few posts explaining one of the major topics I lectured on, the PCP Theorem (PCP stands for Probabilistically Checkable Proofs).
For right now, I’m not even going to state this theorem, since understanding the theorem requires some background information. I’ll provide some of that background in this post, more next post, and then state the theorem in the third. Regardless, it’s not actually the statement of the PCP Theorem that’s important, it’s the consequences of the theorem. If you understand these consequences, you understand a lot of what theoretical computer science is about. Unfortunately I’ve never seen a plain English explanation of the theorem that is accessible to non-computer scientists. I’m hoping the next few posts will help fill this void.
The PCP Theorem, and complexity theory in general, is concerned with the resources required to solve certain problems. For example, how long does it take to multiply two numbers? Obviously if you do it by hand, it takes longer than if you use a calculator. What’s important, however, is that whether you use a pencil and paper, a calculator, or a super computer, the time it takes depends on the length of the numbers. Suppose you multiply two numbers with n digits each. Using the procedure you learned in elementary school, the amount of time it takes is going to be proportional to n2. The same is true for a computer that has been programmed to use the same procedure. As I mentioned once before, faster approaches are known, but these approaches as well can be executed by computers and humans alike.
In computer science (and in other fields too) we often try to identify the fastest procedure, or algorithm, to solve a given problem. Usually algorithms are described by writing a computer program, but this is just a formality. Once a problem has been specified in terms of numbers, or symbols, telling a computer how to solve it isn’t too different from telling a person how to.
You can tell a person to “find Rhode Island on a map”, but you can’t program a computer to do this unless you first specify how the map, and Rhode Island, are represented. If, however, you have a list of cities and the distances between them, you can program a computer to find the shortest route that visits each of the cities. The key is that the problem has been well defined using symbols. In a computer, if you want to something with images (or sounds, smells, etc…), you need to first represent them using combinations of symbols.
So here’s the general story: If you study computer science, you’ll come across with a whole host of nicely specified problems. You’ll learn that a computer can be programmed to solve these problems. Once you get the hang of it, you’ll see that the steps a computer performs when solving these problems are basically the same steps a person would perform. As a result, you’ll understand that it makes sense to study how hard a problem is by determining how many steps it takes to solve, given its length. The main goal of complexity theory is to try to understand why some problems are fundamentally harder to solve than others. So far, this has proved difficult, but complexity theorists have identified many problems that they strongly suspect are hard to solve. In fact, if you could prove that any one of these problems is hard to solve, you would simultaneously prove that all of them are hard to solve, and you would win one million dollars. More on that next time.