Empty Pigeonhole Principle Powers Complexity Theory and Search Problems

Deep Dive

The discussion begins with the obvious statement that if there are more pigeons than pigeonholes, at least two pigeons must share a hole. This concept, known as the pigeonhole principle, is presented as a powerful tool used in computer science problems. The principle is further illustrated by stating that if six pigeons nestle into five pigeonholes, at least two must share a hole.

The narrative then shifts to how the pigeonhole principle applies to situations beyond birds and holes, such as in a packed football stadium where the number of attendees outnumbers the possible four-digit PINs. The source explains that this implies some attendees must share the same PIN, with the pigeons representing fans and the holes representing the 10,000 distinct four-digit PINs. A key implication of this proof is its non-constructive nature; it proves existence but does not provide a method to find the shared PINs.

The conversation moves to computational complexity theory, a field that studies the efficiency of problem-solving. Complexity theorists categorize problems based on shared properties, and the source highlights the creation of new problem classes as a method for unifying previously unconnected research areas. This approach was notably pursued in the 1990s by Christos Papadimitriou and other complexity theorists, aiming to find problems guaranteed to have solutions via non-constructive proofs like the pigeonhole principle. This line of research has reportedly yielded progress in cryptography and algorithmic game theory.

The discussion then introduces a twist on the pigeonhole principle: what happens when there are fewer pigeons than holes? This inverted scenario, where any arrangement must leave some empty holes, is presented as having subtle differences that make it a new tool for classifying computational problems. The source uses the example of a concert hall with fewer seats than possible four-digit PINs to illustrate that some PINs will not be represented.

A critical distinction is drawn between the original and inverted pigeonhole principles concerning the difficulty of checking solutions. While verifying a claim of shared PINs in the football stadium scenario is simple, verifying a claim that no one has a specific PIN in the concert hall scenario requires checking everyone. This difficulty makes the inverted principle more challenging for complexity theorists.

The source details how Papadimitriou and colleagues published a paper on "abundant polynomial empty pigeonhole principle" (APEP) problems, which are search problems guaranteed to have solutions due to the inverted principle, particularly when pigeonholes vastly outnumber pigeons. This class of problems was inspired by Claude Shannon's proof that most computational problems are inherently hard to solve, an argument that relied on the inverted pigeonhole principle without explicitly naming it. The difficulty of proving that specific problems are hard, akin to finding missing bank card pins, is discussed.

The approach of grouping the search for hard problems with other search problems connected to the inverted pigeonhole principle is described as having a self-referential quality. This method offers a new perspective on reasoning about the difficulty of proving computational difficulty. Oliver Korten, a researcher at Columbia, is mentioned as having proven in his first year of graduate school that the search for hard computational problems is mathematically linked to all other problems in APEP.

Korten's work has reportedly led to new results connecting computational difficulty and randomness, with Papadimitriou noting the "amazing richness" and depth of these findings in relation to significant complexity theory problems. The episode concludes by crediting Michael Kenyon and Golo for their assistance and identifying Ben Brubaker as the author of the full article on Quanta Magazine's website.