After Turing, computer scientists began to classify other problems by their difficulty. Harder problems require more computational resources to solve — more running time, more memory. This is the study of computational complexity.
Ultimately, every problem presents two big questions: “How hard is it to solve?” and “How hard is it to verify that an answer is correct?”
Interrogate to Verify
When problems are relatively simple, you can check the answer yourself. But when they get more complicated, even checking an answer can be an overwhelming task. However, in 1985 computer scientists realized it’s possible to develop confidence that an answer is correct even when you can’t confirm it yourself.
The method follows the logic of a police interrogation.
If a suspect tells an elaborate story, maybe you can’t go out into the world to confirm every detail. But by asking the right questions, you can catch your suspect in a lie or develop confidence that the story checks out.
In computer science terms, the two parties in an interrogation are a powerful computer that proposes a solution to a problem–known as the prover–and a less powerful computer that wants to ask the prover questions to determine whether the answer is correct. This second computer is called the verifier.
To take a simple example, imagine you’re colorblind and someone else–the prover–claims two marbles are different colors. You can’t check this claim by yourself, but through clever interrogation you can still determine whether it’s true.
Put the two marbles behind your back and mix them up. Then ask the prover to tell you which is which. If they really are different colors, the prover should answer the question correctly every time. If the marbles are actually the same color–meaning they look identical–the prover will guess wrong half the time.
“If I see you succeed a lot more than half the time, I’m pretty sure they’re not” the same color, Vidick said.
By asking a prover questions, you can verify solutions to a wider class of problems than you can on your own.
In 1988, computer scientists considered what happens when two provers propose solutions to the same problem. After all, if you have two suspects to interrogate, it’s even easier to solve a crime, or verify a solution, since you can play them against each other.
“It gives more leverage to the verifier. You interrogate, ask related questions, cross-check the answers,” Vidick said. If the suspects are telling the truth, their responses should align most of the time. If they’re lying, the answers will conflict more often.
Similarly, researchers showed that by interrogating two provers separately about their answers, you can quickly verify solutions to an even larger class of problems than you can when you only have one prover to interrogate.
Computational complexity may seem entirely theoretical, but it’s also closely connected to the real world. The resources that computers need to solve and verify problems–time and memory–are fundamentally physical. For this reason, new discoveries in physics can change computational complexity.
“If you choose a different set of physics, like quantum rather than classical, you get a different complexity theory out of it,” Natarajan said.
The new proof is the end result of 21st-century computer scientists confronting one of the strangest ideas of 20th-century physics: entanglement.
The Connes Embedding Conjecture
When two particles are entangled, they don’t actually affect each other–they have no causal relationship. Einstein and his co-authors elaborated on this idea in their 1935 paper. Afterward, physicists and mathematicians tried to come up with a mathematical way of describing what entanglement really meant.
Yet the effort came out a little muddled. Scientists came up with two different mathematical models for entanglement–and it wasn’t clear that they were equivalent to each other.