“The pigeonhole principle is a theorem that elicits a smile,” said Christos Papadimitriou, a theoretical computer scientist at Columbia University. The pigeonhole principle applies to any situation where items are assigned to categories, and the items outnumber the categories. “Nonconstructive” proofs, like ones based on the pigeonhole principle, don’t have this property. Questions like this one, about the most efficient way to solve problems, are at the heart of the branch of computer science known as computational complexity theory. That line of work has led to important progress in disparate fields of computer science, from cryptography to algorithmic game theory.