Get the latest tech news
Why Pigeons at Rest Are at the Center of Complexity Theory
When pigeons outnumber pigeonholes, some birds must double up. This obvious statement, and its inverse, have deep connections to many areas of math and computer science.
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. 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. To understand the empty-pigeonhole principle, let’s go back to the bank-card example, transposed from a football stadium to a concert hall with 3,000 seats—a smaller number than the total possible four-digit PINs.
Or read this on Wired