When it comes to hard problems, computer scientists seem to be stuck. Consider, for example, the notorious problem of finding the shortest round-trip route that passes through every city on a map exactly once. All known methods for solving this “traveling salesperson problem” are painfully slow on maps with many cities, and researchers suspect there’s no way to do better. But nobody knows how to prove it.
For over 50 years, researchers in the field of computational complexity theory have sought to turn intuitive statements like “the traveling salesperson problem is hard” into ironclad mathematical theorems, without much success. Increasingly, they’re also seeking rigorous answers to a related and more nebulous question: Why haven’t their proofs succeeded?
This work, which treats the process of mathematical proof as an object of mathematical analysis, is part of a famously intimidating field called metamathematics. Metamathematicians often scrutinize the basic assumptions, or axioms, that serve as the starting points for all proofs. They change the axioms they start with, then explore how the changes affect which theorems they can prove. When researchers use metamathematics to study complexity theory, they try to map out what different sets of axioms can and can’t prove about computational difficulty. Doing so, they hope, will help them understand why they’ve come up short in their efforts to prove that problems are hard.
In a paper published last year, three researchers took a new approach to this challenge. They inverted the formula that mathematicians have used for millennia: Instead of starting with a standard set of axioms and proving a theorem, they swapped in a theorem for one of the axioms and then proved that axiom. They used this approach, called reverse mathematics, to prove that many distinct theorems in complexity theory are actually exactly equivalent.
“I was surprised that they were able to get this much done,” said Marco Carmosino, a complexity theorist at IBM. “People are going to look at this and they’re going to say, ‘This is what got me into metamathematics.’”
Pigeon Proofs
The story of the reverse-mathematics paper began in the summer of 2022, when Lijie Chen, a complexity theorist now at the University of California, Berkeley, was wrapping up his doctorate. He found himself with a lot of extra time on his hands and decided to devote a few months to reading up on metamathematics.
Lijie Chen thought of a way to invert the relationship between two mathematical theorems. Hongxun Wu
“Because I was graduating, I didn’t have much research to do,” Chen said. “I was figuring I should learn something new.”
As he read, Chen began thinking about a branch of complexity theory called communication complexity, which studies the information two or more people must exchange to accomplish certain tasks. One of the simplest problems in communication complexity, called the “equality problem,” is like a collaborative game. Two players start with separate strings of 0s and 1s (or bits). Their goal is to use as little communication as possible to determine whether their strings are the same. The simplest strategy is for one player to just send their full string for the other to check. Is there any way to do better?
... continue reading