Sep 10, 2026 · 12 min · 7 segments
Researchers have used metamathematical techniques to show that certain theorems that look superficially distinct are in fact logically equivalent. The article…
[upbeat music] 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 in 2024, three researchers took a new approach to this challenge.
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 the axiom.
They used it to prove that many distinct theorems in complexity theory are actually exactly equivalent.
Marco Carmosino, a complexity theorist at IBM, says he was surprised that they were able to get this much done.
[upbeat music] 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 in 2024, three researchers took a new approach to this challenge.
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 the axiom.
They used it to prove that many distinct theorems in complexity theory are actually exactly equivalent.
Marco Carmosino, a complexity theorist at IBM, says he was surprised that they were able to get this much done.
Every episode on Radar is fully transcribed, speaker-labeled, and rich with metadata. Here is a taste of this one. Try Radar for free to see the rest.
The rest of this transcript — segmented and speaker-labeled, so you land on the exact moment something was said
All 7 segments — the transcript broken into labeled sections, every ad read marked
All 18 topics — jump to every other episode discussing the same subject
Every related episode — other shows Radar links to this one
No account is needed to search Radar.
