Thread by @QuantaMagazine

Computer scientists often study how difficult certain problems are to solve. But a subset of them are fascinated by a more complex question: How hard is it to determine how hard those problems are?

This field is known as meta-complexity. 🧵

Meta-complexity focuses on the differences in difficulty between certain types of computational problems. For example, Hamiltonian paths (paths that pass through every point of a graph) become exponentially harder to compute as the graphs grow larger.

Eulerian paths, which go over every edge of a graph exactly once, become harder as graphs get larger, but at a rate much slower than their Hamiltonian cousins.

The differences in Eulerian and Hamiltonian paths illustrate a foundational problem in computer science. Why should some problems be so much harder than others to solve? And is there a hidden algorithm that would solve all of these difficult-to-solve conundrums?

Complexity researchers discovered they could reformat computational problems using the language of circuit complexity, with circuits representing Boolean functions. They hoped to use this strategy to prove that some easy-to-check problems were difficult to solve.

Attempts to prove hardness ran up against the natural proofs barrier, a result by Alexander Razborov and Steven Rudich that essentially meant that mathematicians wouldn’t succeed if they used techniques they already had.

To some meta-complexity researchers, however, the natural proofs barrier looked like an opportunity. They found that a certain kind of unclassified algorithm could be used to construct a powerful “learning” algorithm that can spot patterns in seemingly unrelated numbers.

The potential of powerful learning algorithms made researchers take notice, and there have recently been several new breakthroughs in the field that come closer to classifying certain problems that have mystified scientists for years, extending a timeline that dates back to 1921.

To learn more about the field of metacomplexity and its breakthroughs, read @benbenbrubaker’s feature for Quanta: quantamagazine.org/complexity-the…