Why Pigeons at Rest Are at the Center of Complexity Theory
1 min read
Summary
The pigeonhole principle is a simple mathematical concept that states that if six items are put into five containers, at least two items will end up in the same container.
While this may sound like a simpleminded party trick, it has become a non-trivial tool for computer scientists to prove the hidden relationships between different problems in theoretical computer science.
The principle can be applied in various everyday situations, such as in attenuated password reuse in a crowded stadium to having the same set of digits being reused in different passwords.
Through thought experiments, a computer scientist has extrapolated the simple principle into a whole new avenue of research in complexity theory, where problems that are guaranteed to have solutions because of the pigeonhole principle have been dubbed “APEPP” (abundant polynomial empty-pigeonhole principle) problems.
This new class of computational problems has led to new insights into old problems that have been around for over 50 years.
The simplicity of the concept has led the computer scientist to quip that “It goes to the bone of important problems in complexity.
