Halting Problem & Quantum Entanglement 2020 Breakthrough result [MIP*=RE]

Описание: This video explains the MIP*=RE result. We skip the proof details, just explain what the result means.

Please leave comments in the comment section if something is unclear.

The links mentioned in the video:

1) Proof that the halting problem can't be solved:
   • Proof That Computers Can't Do Everything (...  

2) Using the entanglement, see here:    • Gamification of Bell's Theorem  

Also, here's a general primer to quantum physics:
   • Visualization of Quantum Physics (Quantum ...  

3) Proof that PSPACE contains P and is contained in EXP: TBA sometime

Chapters:
0:00 Part 1: Decision problems
3:13 Part 2: Complexity classes
7:32 Part 3: Verification
12:57 Part 4: More verification power
17:51 Part 5: Some implications

Some more explanations:

Part 3:

We require the verifier to run in polynomial time. This has the usual definition with respect to the input's size. This constraints the size of the proof sent by the prover, since reading 1 character costs 1 time unit.

In the video we make a distinction between honest and malicious provers. Sometimes it is defined differently: there's only one kind of prover, and it always wants to get the verifier to accept. For w that is in L, it gets the verifier to accept by cooperating and behaving nicely. For w outside of L, it tries to get the verifier to accept by cheating.

Part 4:

MIP: In previous games, the verifier faces a single prover. Its goal was to be able to detect if the prover is lying or telling the truth. For languages inside PSPACE, the prover could do that. But languages outside PSPACE are more complicated. For these languages, the verifier can't tell if the prover is lying or telling the truth.
In MIP we help the verifier more by having two provers. The verifier can now judge if a response is a lie not just by examining the response itself, but by comparing what the two provers say. If they respond to the same question differently, one of the responses must be a lie, and the verifier can reject immediately.
This added ability to detect lies helps it verify more complicated languages - all languages in the large class called NEXP.

MIP*: Here there's something non-intuitive going on. We help the provers by giving them a quantum device, but it turns out it actually helps the verifier. The details here are complicated, but we may explore them further in future videos.

One frequent question is why the provers use the entanglement at all, even the honest ones. The reason is that the verifier forces them to use the entangelement.

To see why, consider the non-isomoprhism example: the verifier gives the prover a computational challenge. This challenge is designed such that the prover can win only if the graphs are non-isomorphic.

The quantum entanglement opens the door for new kinds of challenges that the provers can win. It wasn't obvious if any of them are useful for our purposes, but then one was discovered: there exists a challenge such that for a given program p:
1) The provers can only win if p halts.
2) And they can only win if they cooperate via the entanglement.
Condition (2) is logically important: without it the game would have been possible with MIP as well. The provers can choose not to use the entangelement, but then they'll lose. We assume the provers want to win.