The role of guessing in complexity theory
Edward Vul and Harold Pashler are psychologists. They have discovered something intriguing about guessing.
Today I want to share a draft of a piece on the question that is geared toward non-specialists. It views the famous question as a question about “guessing.” I would like to hear from you about what you think of it.
As I was preparing this, I ran across Vul and Pashler’s paper on guessing, which I thought would be fun to share; perhaps you missed it initially as I did. Consider this question:
What percentage of the world’s airports are in the USA?
The idea is to guess at the answer. Then take a minute, drink a soda or a cup of coffee, and make another guess. The claim is that the average of the two guesses is usually more accurate the original guess. They show by an empirical study that the increase in accuracy is about 6.5 percent. Waiting weeks ups the accuracy much more—the claim is it is now about 16 percent. Here is a chart from their paper:
Enough on actually guessing, let’s turn to a discussion of our problem as a question about potentially guessing.
The Power of Guessing
Some scientific questions are fundamental to our understanding of life, the universe, and/or everything—here by `everything’ we mean the world of mathematical laws. In physics there is the question of what is beyond the event horizon of a black hole—does it lead to another world? In biology there is the question of what causes cells to differentiate: how do they know to change as they divide? In chemistry there is the question of how do proteins fold into three dimensional structures—how do they know how to form these complex shapes? In computer science there is the question of what is the power of guessing—why do we seem unable to solve certain important computational problems efficiently without guessing?
The latter question about the power of guessing is called the question. Forget for now what these symbols mean; for now view them as a place-holder for our fundamental question.
An example of the type of problem that is captured by the question is a simple combination lock. I mean the kind of lock that is used to secure anything from our lockers at the gym to classroom equipment to our bicycles. Each lock typically has three numbers that are the combination—yes expensive ones can have more. To open the lock you must dial each number in the correct order: first turn the lock clockwise to 9, then counterclockwise to 6, then clockwise again to 46. In this case your secret combination is 9,6,46—my birthday—probably not the best choice for a secret. Anyone who wants to open the lock must know these numbers in the correct order. If they try 6,9,46 the lock will refuse to open.
The opening of a combination lock captures the essential features of the type of problems we consider in the question. There is a secret: in the combination lock it is the sequence of the three numbers. There are lots of secrets possible: if each number is between 0 and 99, then there are
combinations possible. If you do not know the combination lock’s secret, you will take a very long time trying one combination after the other, until you find the correct one. At one spin of the lock per second, you will succeed in about one month of trying.
The pivotal feature is that should you try the correct combination—9,6,46—the lock will open. You will know immediately that you have the correct secret combination to the lock. This is critical; without it there is no hope at all in even trying to find the secret.
What does this have to do with guessing? Everything. Suppose that you were a great guesser, then the combination lock problem would be simple. You would think, make your guess, and then try and see if the lock opens. If you were a terrific guesser, then you would open the lock in one try. Pretty neat.
The question asks, not for mechanical combination locks, but for digital problems, are there computational algorithms that are great guessers? Faced with a digital version of a combination lock, is there an algorithmic way to guess solutions?
One way you could be a terrific guesser for locks would be to have X-ray vision. By analyzing the structure of the hidden tumblers, you could find the combination. What makes the digital problems so surprising is that we already have the X-ray vision—everything that specifies an instance of the problem is given to us. The challenging question is whether there is something about the structure of the instance that enables us to see the answer without trying a multitude of combinations.
The ramifications of this question are immense, and I would argue it is at least as important to our understanding of the universe as black holes, cell differentiation, and protein folding. There are two possibilities: there is a digital way to be a terrific guesser, or there is no way to have such a guesser. The first is denoted by —there are good guessers. The second is denoted by —there are no good guessers. The fancy symbol just means that two things are not equal.
Today we have no idea which is true: does or does ? The question is important precisely because the different answers would place us in two very different worlds.
In the first world there would be algorithms that could guess the solutions to problems. Such algorithms would change our world. Computer security would be gone. Messages sent over the Internet, for example, could be read by anyone. There would be no convenient secrecy, no digital combination locks.
There would be good consequences too of . We could design algorithms that could solve almost any problem—not quite any—more on that later. But most. This would lead to immensely powerful algorithms. Some believe that this would lead to machines that could out-think humans. Certainly for many tasks these algorithms could improve the performance of everything that we do today by computer.
In the second world there would not be algorithms that could guess the solution to any problem. Computer security would be safe, at least in some forms. Messages could be sent over the Internet in complete safety from being read by those without the secrets.
There would be bad consequences too of . There would be problems that no algorithm could solve in any reasonable time. These problems abound in science and technology, and they would have no reasonable solutions. Without the power to guess correctly, these problems would be impossible. At best we would be able to “come close,” which is OK for some practical problems, but not for many others.
The question is: which world do we live in? Are there powerful guessing algorithms that can solve almost anything? Or are there problems that defeat any algorithm? We do not know. The solver of this problem, the person who shows that or shows that , would dramatically change our understanding of the world. They would also collect a million dollars from the Clay Institute, since this question is one of their six remaining Millennium Prize Problems.
Of course the above is a simplification of the actual situation as I have discussed before here, referencing Russell Impagliazzo’s detailed description of five different algorithmic worlds. I plan, if I expand on this piece, to make this clear. There is also Scott Aaronson’s survey of Nature’s possible ability to solve NP-complete problems.
What do you think about this start? Too simple? Too hard? Just right? Let me know. What other good references are there besides the above two, and how to refine them?
By the way the answer to the airport question is about 30 percent—but I guess you knew that.