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.

How Hard Is It to Untie a Knot?

Exploring the distant universe, the insides of cells, the abstractions of math, the complexity of information itself, and much more, The Quanta Podcast is a tour of the frontier between the known and the unknown. In each episode, Quanta Magazine Editor-in-Chief Samir Patel speaks with the minds behind the award-winning publication to navigate through some of the most important and mind-expanding questions in science and math. Quanta specifically covers fundamental research — driven by curiosity, discovery and the overwhelming desire to know why and how. Join us every Tuesday for a stimulating conversation about the biggest ideas and the tiniest details.(If you've been a fan of the Quanta Science Podcast, it will continue here. You'll see those episodes marked as audio edition episodes every two weeks.)