They say a bird in the hand is worth two in the bush, but for computer scientists, two birds in a hole are better still. That’s because those cohabiting birds are the protagonists of a deceptively simple mathematical theorem called the pigeonhole principle. It’s easy to sum up in one short sentence: If six pigeons nestle into five pigeonholes, at least two of them must share a hole. That’s it — that’s the whole thing.
“The pigeonhole principle is a theorem that elicits a smile,” said Christos Papadimitriou, a theoretical computer scientist at Columbia University. “It’s a fantastic conversation piece.”
But the pigeonhole principle isn’t just for the birds. Even though it sounds painfully straightforward, it’s become a powerful tool for researchers engaged in the central project of theoretical computer science: mapping the hidden connections between different problems.
The pigeonhole principle applies to any situation where items are assigned to categories, and the items outnumber the categories. For example, it implies that in a packed football stadium with 30,000 seats, some attendees must have the same four-digit password, or PIN, for their bank cards. Here the pigeons are football fans, and the holes are the 10,000 distinct possible PINs, 0000 through 9999. That’s fewer possibilities than the total number of people, so some people must have the same digits.
This proof is notable not just for its simplicity, but also for what it leaves out. Many mathematical methods for proving that something exists are “constructive,” meaning they also show you how to find it. “Nonconstructive” proofs, like ones based on the pigeonhole principle, don’t have this property. In the football stadium example, knowing that some people must have the same PINs won’t tell you what they are. You can always go through the stands asking each person in turn. But is there a simpler way?
Questions like this one, about the most efficient way to solve problems, are at the heart of the branch of computer science known as computational complexity theory. Complexity theorists study such questions by lumping problems into classes based on certain shared properties. Sometimes the first step toward a breakthrough is simply defining a new class to unite problems that researchers hadn’t previously studied together.
That’s what happened in the 1990s, when Papadimitriou and other complexity theorists began to study new classes of problems, in which the goal is to find something that must exist because of the pigeonhole principle or another nonconstructive proof. That line of work has led to important progress in disparate fields of computer science, from cryptography to algorithmic game theory.
