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:

Also, here's a general primer to quantum physics:

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.

[yoshi-csib]

My heart stopped for a second when the halting solver appeared but then I realized the implication a millisecond later and was very relieved

[anselmschueler]

It was quite a shock when the malicious provers walked to meet each other.

[Wonders_of_Reality]

16:00 — As an animator, I find those malicious provers adorable! Very nicely done! Simple, and yet you conveyed the emotions perfectly! Love it!

[MrCreeperk]

I was just in my computational theory class this morning thinking about how this type of material is really underrepresented in educational youtube even though it's so interesting and generally applicable. Super nice to find this!

[BasteGd]

When I discovered this channel in 2013, I was still a middle school student. Now I have a B.S. in Computer Science. Time flies! :-)

[theopantamis]

I think we all underestimate the value of having such video on the internet.

Animated explanation like this one are highly valuable, they make the results found more clear for more people, so more people can think about what's next and share more new idea that may move the humankind forward.

So thank you for this video and all the others of this channel !

[angel-ig]

Wow, what a nice summary! You explain Big-O Notation, time and space complexity, complexity classes, P vs NP and this new result (and that final theorem that derives from it, which was super brilliant) in probably the best way done in YouTube till now. Keep it up! I really want to see the next TBA videos... :)

[TimJSwan]

To anyone who thinks you can't prove that a program doesn't halt: you can. You just can't prove all of them.

[Irondragon]

This was a beautiful watch. The voice, the animations, the pacing, the topic.

[AvianYuen]

Always a pleasure when you upload. I don't understand all of this, but I can appreciate the achievement of the original authors (and your work!)

[shinqqing]

Damn.. I was like why did I get recommended this video and then I looked up your uploaded videos and it looks like I watched your video on halting problem years ago when I was still a student. Thank you, it really helped me back then!

[McMurchie]

This is multiple lifetimes of knowledge in 20 minutes.

[Lemon_Inspector]

It would be nice if you'd reference the paper this result came from in the description. I mean, personally I'm intimidated by the table of contents already, but there's a non-zero chance somebody who hasn't heard of the topic but has the capacity to understands it gets this video recommended by coincidence.

[proloycodes]

some days, i wonder what i am even doing in youtube, but every once in a while, gems like these appear in my feed that connect two seemingly different things, and causes my mind to blow up. thank you for that, kind peron in the internet...

[zacw]

I'm so glad you made this! I learnt about it when it happened but couldn't find much online that I could understand with just my high school maths knowledge. Keep making awesome content!

[codegeek]

What a time to be alive; this is terrifying that we're able to reason so much about _what can be figured_

[Julian-tfnj]

Thank you for another awesome video. What I'd LOVE TO SEE is a video about *why using quantum entanglement to "coordinate" (as the Prover machines do) is not actual "communication".*
I'm aware from physics that one cannot transfer information by means of quantum entanglement, but I'd love to see an in-depth explanation about it - and in particular develop better intuition for what this _"coordination that is NOT communication"_ really is about (maybe it'd be good to have a term for it?)

[FineDesignVideos]

Great video! There was also a recent work called "Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs" that adds to the mystique of this work by giving a neat combinatorial problem that doesn't feel like it should be undecidable but is.

[UCFcXDsWoHaZmXomKVxvuA]

Top tier man, as always! This channel is so well curated and it talks about the coolest things... What is your background in readings and education? Can you suggest us any book that you've read, so we could learn more?

[CyberAnalyzer]

I cannot wait for the video about quantum entanglement! Why it isn't possible to communicate with it is extremely fascinating!