For more than 50 years, researchers in the field of computational complexity theory have tried, without much success, to translate intuitive statements like “the traveling salesman problem is hard” into ironclad mathematical theorems. Increasingly, they are also looking for a hard answer to a related and more obscure question: Why didn’t their proofs succeed?
This work, which treats the process of mathematical proof as the object of mathematical analysis, is part of a famously intimidating field called metamathematics. Metamathematicians often examine the basic assumptions, or axioms, that serve as the starting point for all proofs. They change the principles they start with, then explore how these changes affect the theorems they can prove. When researchers use metamathematics to study complexity theory, they try to figure out what different sets of axioms about computational difficulty can and cannot prove. They hope that doing so will help them understand why they failed in their attempts to prove that the problems are hard.
In a paper published last year, three researchers took a new approach to this challenge. He reversed the formula that mathematicians have used for millennia: Instead of starting with a standard set of axioms and proving a theorem, he swapped a theorem for an axiom and then proved that axiom. He used this approach, called reverse mathematics, to prove that many different theorems in complexity theory are actually exactly equivalent.
“I was surprised that they were able to do so much,” said Marco Carmosino, a complexity theorist at IBM. “People will look at it and say, ‘This is what attracted me to metamathematics.'”
pigeon proof
The story of the reverse-math paper began in the summer of 2022, when Lizzie Chen, a complexity theorist at the University of California, Berkeley, was completing her doctoral studies. He found that he had a lot of spare time and decided to devote a few months to reading up on metamathematics.
“Since I was an undergraduate, I didn’t have much research to do,” Chen said. “I was thinking I should learn something new.”
While reading, Chen began thinking about a branch of complexity theory called communication complexity, which studies the information exchanged by two or more people to accomplish certain tasks. One of the simplest problems in communication complexity, called the “similarity problem”, is like a cooperative game. Two players start with different strings of 0s and 1s (or bits). Their goal is to use as little communication as possible to determine whether their strings are identical. The simplest strategy is for one player to send his entire string to the other player for checking. Is there any way to do better?
Complexity theorists proved decades ago that the answer is no. To solve the parity problem, players need to send, at least, a number of bits equal to the number of the complete string. Theorists say that this string length is a “lower bound” on the amount of communication required.
Chen’s focus was not on the lower bound of the equivalence problem—he was interested in how researchers proved it. All known proofs depend on a simple theorem called the pigeonhole principle, which states that if you put some number of pigeons into a small number of holes, at least one hole must have more than one bird in it. This may seem self-evident, but it can be a surprisingly powerful tool in complexity theory and beyond.
Chen found an intriguing hint that the connection between the similarity problem and the pigeon-hole principle might also go the other way. It is easy to use the pigeonhole principle to prove the lower bound of the equality problem. Can you use lower bounds to prove the pigeonhole theorem instead?
uncanny resemblance
Chen discussed his idea with Jiatu Li, then an undergraduate at Tsinghua University, with whom Chen had recently collaborated on another paper. In order for the relationship to be rigorous, they must choose a set of principles to work by. Metamathematics researchers prefer to use axioms that are more restricted than general axioms. These weak axioms make it easier to determine the exact relationships between different theorems. Chen and Li decided to work with a popular set of axioms called PV1PV1 Strong enough to prove some important theorems about computational complexity on its own. Add a specific version of the pigeonhole principle as an additional theorem, and you can also prove a lower bound of the similarity problem. In December 2022, Li and Chen formally showed that, as Chen suspected, the proof also works with two interconnected theorems.
<a href