MIP* = RE is not a typo. It is a groundbreaking discovery and the catchy title of a recent paper in the field of quantum complexity theory. Complexity theory is a zoo of “complexity classes”—collections of computational problems—of which MIP* and RE are but two.
The 165-page paper shows that these two classes are the same. That may seem like an insignificant detail in an abstract theory without any real-world application. But physicists and mathematicians are flocking to visit the zoo, even though they probably don’t understand it all. Because it turns out the discovery has astonishing consequences for their own disciplines.
In 1936, Alan Turing showed that the Halting Problem—algorithmically deciding whether a computer program halts or loops forever—cannot be solved. Modern computer science was born. Its success made the impression that soon all practical problems would yield to the tremendous power of the computer.