A visit from Alice and Bob

One day, two mysterious people stop by your house and announce that they’re capable of performing extremely complex computations. You’re thinking about slamming the door in their faces but, curiosity piqued, you ask: how complex? They smile slyly.

At least any problem that is solvable using polynomial space, they say. You’re incredulous: this not only includes all NP-complete problems but all problems that can be solved by quantum computers and even problems like deciding who has a winning move in Chess and Go (given a polynomial bound on the number of rounds). But amidst your double take you remember from your complexity theory class that you can efficiently verify whether someone can solve these incredible problems by using an interactive proof.

You quickly run through an interactive proof with them; asking these two people (who are called Alice and Bob, apparently) questions about low degree polynomials over finite fields in the way you learned about in complexity class. Holy smokes, Alice and Bob are really smart! They have convinced you beyond reasonable doubt that they can solve PSPACE complete problems.

Color me impressed, you say.

Oh, but that’s not the end of it, say Alice and Bob. Have you heard of the 1980’s result of Babai, Fortnow, and Lund? If you put us into separate rooms, and cross-interrogate us, we can convince you that we’re capable of solving way harder problems. NEXP-complete problems, in fact.

You hesitate, but just for a moment. NEXP problems: these are NP problems writ large — exponentially large. You have always wanted to solve the travelling salesman problem on a graph with exponentially many vertices and edges, actually. A chance to finally know the answer is too good to pass up.

Come in, you say. You put Alice and Bob into separate rooms in your house. They’re isolated; there is no way for Alice and Bob to talk to each other, and they can only talk to you. You had forgotten how this BFL protocol works but you look it up online to quickly refresh your memory of it. Ah, yes; more low-degree polynomials. That’s always the magic sauce.

You do the cross-interrogation. By golly, Alice and Bob are really acing your tests! They can really do it, solving NEXP-complete problems. They come out, and you are not quite sure from what plane of existence these computational gods have come from. Still in a daze, you ask: erm… can I get you some tea, or cookies?

They look at each other. Thanks, Alice says, but we’re not done yet.

Whoa, whoa, whoa, you stammer. You guys, this is totally unreal. I’m probably just dreaming. But, as crazy as this all is, I still know one thing. There is no way you two can convince me that you can solve any problems beyond NEXP. Babai, Fortnow, and Lund proved that the class of problems solvable by multiprover interactive proofs is exactly equal to NEXP. You might be able to do more, but you wouldn’t be able to convince me of it.

Bob has a look of amusement on his face, as if he were listening to a child. Have you heard of something called quantum entanglement?

You scrunch your face. Oh, I read something about it recently online. It’s like this spooky action at a distance that Einstein disliked? And then there was this John Bell who proved that…

Alice, getting impatient, cuts you off. Yes, yes, that classical physics can’t give a local explanation of quantum correlations. Anyways, Bob and I, we’re quantumly entangled.

You stare.

Bob laughs. No, we aren’t telepathic or anything. Quantum entanglement doesn’t allow you to send signals faster than the speed of light. But, it does allow us to take advantage of correlations that are stronger than any classical correlations. Babai, Fortnow, and Lund’s proof, on the other hand, only concerns classical provers, who don’t have access to these correlations. Here, let’s try this. Here’s a multiprover interactive protocol that you might not have heard of, but it’s supposed to be performed with entangled provers like Alice and me.

He hands you a thick preprint of 120 pages. You thumb through it, marvelling.

Hold on, you say. This quantum entanglement thing might not allow you two to communicate, but it might allow you to correlate your responses in a way to fool me, and convince me that you can solve really hard problems, even though you can’t. This all seems rather fishy.

Alice looks at Bob. Our friend here is a bit slow, isn’t she?

Bob chuckles. Well, she is only a polynomial time verifier. Her job is to be skeptical.

Bob turns to you. Don’t worry. This protocol here, it’s sound against entangled provers, meaning that we can’t use entanglement against you. If we don’t know the right answers, you’ll be able to catch us lying. The entanglement is a resource to help all of us: we’ll need the entanglement in order to convince you that we’ve solved the NEEXP problems successfully.

Your heart stops. NEEXP? Nondeterministic DOUBLY exponential time? If in the computational universe, PSPACE is going to the moon, and NEXP is flying beyond Pluto, then NEEXP is venturing to the Andromeda galaxy. A NEEXP problem is to solve the traveling salesman problem on graphs with doubly exponentially many vertices. This graph is so big, that you don’t even have enough memory in your own head to remember the precise number of vertices in the graph. Your only connection to this graph is an unintelligible computer program that spends an exponential amount of time spitting out ANOTHER computer program, which then you could run for DOUBLY exponential time to spit out the graph. Of course, you don’t have this kind of time. But Alice and Bob do, apparently.

Your heart goes from 0 to 60. You rush them back into the separate rooms. You take another look at the preprint. It’s 120 pages full of quantum stuff, but once again polynomials play a star role.

You run the protocol with them. It’s an arcane, alien ritual. You feel like the wizard’s apprentice, summoning some deep, extraordinary powers beyond your capability to control. You worry if perhaps you’ve gone a step too far.

After polynomially many rounds, the protocol ends. Alice and Bob emerge from their rooms, and even these gods — surely they must be gods — look a little worn out. You’re sitting there, staring at the result in front of you.

$x \in L$.

And you believe it.

So how about tea and cookies? says Alice brightly.