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.The story <a href="https://www.quantamagazine.org/how-a-problem-about-pigeons-powers-complexity-theory-20250404/">How a Problem About Pigeons Powers Complexity Theory</a> first appeared on Quanta Magazine.

<description>
 &lt;p&gt;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.&lt;/p&gt;&lt;p&gt;The story &lt;a href="https://www.quantamagazine.org/how-a-problem-about-pigeons-powers-complexity-theory-20250404/"&gt;&lt;strong&gt;How a Problem About Pigeons Powers Complexity Theory&lt;/strong&gt;&lt;/a&gt; first appeared on Quanta Magazine.&lt;/p&gt;
 </description>

In a packed stadium with 30,000 seats, some attendees must have the same four-digit password, or PIN, for their bank cards. That’s because of a mathematical theorem that has spurred progress throughout computer science.

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.

The story <a href="https://www.quantamagazine.org/how-a-problem-about-pigeons-powers-complexity-theory-20250404/">How a Problem About Pigeons Powers Complexity Theory</a> first appeared on Quanta Magazine.

The Quanta Podcast

Audio Edition: How a Problem About Pigeons Powers Complexity Theory

Audio Edition: How a Problem About Pigeons Powers Complexity Theory

Description