How a Problem About Pigeons Powers Complexity Theory
1 min read
Summary
The pigeonhole principle can be mathematically summarized as: if six objects are put into five boxes, then two objects must be in one box.
The deceptively simple theorem can now be used as a powerful tool for classifying computational problems in computer science, including in cryptography and algorithmic game theory.
In January 2020, computer scientist Christos Papadimitriou began thinking about a variant of the pigeonhole principle, which he dubbed the “empty-pigeonhole” principle, which states that if there are fewer boxes than objects, then some boxes must remain empty.
Papadimitriou developed the idea with graduate student Oliver Korten, who showed that the search for “hard” computational problems, ones that are inherently difficult to solve, was intimately linked to other problems guaranteed to have solutions by the empty-pigeonhole principle.
Korten’s insight opened up new connections between computational difficulty and randomness, and prompted a flurry of new results.
