What Happened to the Surprising Theorems?
Computational Complexity 2019-08-20
Twenty-five years ago Peter Shor presented a polynomial-time factoring algorithms for quantum computers. For Peter, it was a simple translation of a quantum algorithm due to Dan Simon. For the rest of us, it was a shock, while we knew quantum could do some seemingly artificial problems exponentially faster, no one expected a natural problem like factoring to fall so quickly. I remember remarking at the time that Shor bought quantum computing twenty years, now I would say fifty.
That may have been the last time I was truly shocked by a theorem in theoretical computer science. I've been shocked by proofs, that Primes are in P, Undirected connectivity in Log space, NEXP not in ACC0, Graph Isomorphism in quasi-polynomial time. But the theorems themselves all went in the directions we expected.
In the ten years before Shor we had plenty of surprises, interactive proofs, zero-knowledge proofs, probabilistically checkable proofs, nondeterministic space closed under complementation, hardness versus randomness, the permanent hard for the polynomial-time hierarchy. It seemed to come to a hard stop after Shor.
There have been some mild surprises, the Hadamard isn't rigid, holographic algorithms, the complexity of Nash equilibrium, QIP = PSPACE, and many others. But nothing that has made us rethink the complexity world.
This reflects the maturity of our field. How many shocking theorems have we seen recently in math in general? We're shocked by proofs of the Poincaré conjecture and Fermat's last theorem but both went in the expected direction.
We will have some shocking theorem in the future, maybe Factoring in P or L = NL. To be truly shocked it would have to be something I can't even imagine being true today.