By January 2020, Papadimitriou had pondered the pigeonhole principle for three decades. Yet, a casual chat with a collaborator sparked a fresh insight—a simple twist that no one had seriously examined before: What happens if there are fewer pigeons than holes? Instantly, the answer seemed clear. Some holes must remain empty. But could flipping the pigeonhole principle upside down reveal surprising mathematical truths?
This “empty-pigeonhole” principle might sound like just a repackaging of the classic idea. It’s not. Its subtle shift has opened new doors in understanding complex computational problems.
To grasp this, imagine a concert hall with 3,000 seats filled with people, compared to the vast number of possible four-digit PIN codes. Thanks to the empty-pigeonhole principle, some PINs simply don’t exist among the crowd. The catch? Finding a missing PIN feels as tedious as asking every person what their code is—hardly efficient.
The twist lies in verification. Picture a stadium where two fans share the same PIN—that claim is easy to check. But what if someone asserts that no one has the PIN 5926 in the concert hall? To confirm that, you’d need to quiz every single attendee. This challenge daunts complexity theorists because it turns a simple idea into a tough problem.
Just two months after this insight, Papadimitriou discussed it with a prospective graduate student. That conversation became poignant—it was his last face-to-face talk before the world shut down due to Covid-19. Confined indoors during lockdown, he delved deeper into how the empty-pigeonhole principle reshapes complexity theory. His team later published a paper on search problems guaranteed to have solutions thanks to this principle. They focused on cases where holes outnumber pigeons by a wide margin. In true complexity theory fashion, they named this concept APEPP: “abundant polynomial empty-pigeonhole principle.”
One problem they explored echoed a groundbreaking 70-year-old proof by Claude Shannon, a computer science legend. Shannon demonstrated that most computational problems are inherently tough using reasoning tied to the empty-pigeonhole principle (though he never called it that). For decades, scientists have hunted for specific hard problems but never found concrete proof. Like elusive missing PINs, these hard problems exist—just out of reach.
Until now, the search for difficult problems wasn’t seen as a search problem itself. Papadimitriou’s fresh perspective treats that pursuit mathematically, layering complexity theory with a self-reflective twist. This breakthrough offers a new lens on why proving the difficulty of computational problems remains one of science’s grand challenges.