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 C...
2) Using the entanglement, see here: • Gamification of Bell's...
Also, here's a general primer to quantum physics:
• Visualization of Quant...
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.

[@anselmschueler]

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

[@Wonders_of_Reality]

Look how lively they’re animated.

[@nzuckman]

I also found it quite jarring hahaha

[@luckabuse]

bigger shock that particle can be sent through the wall and it is not considered a communication :-D

[@anselmschueler]

@@luckabuse No particle is ever sent through a wall. Two particles are entangled.

[@luckabuse]

@@anselmschueler what does entanglement mean to you? The particle is split in two: one flies in one direction and the other in other direction. There is a wall between those points.

[@yoshi-cs6ib]

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

[@Julian-tf8nj]

Same here, lol !!!

[@circumplex9552]

"HEYYYYY HEYYYY HE- ohhhhh"

[@otesunki]

same

[@sudhakarg8921]

+me

[@GerhardTreibheit]

Why

[@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!

[@MrCreeper20k]

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!

[@Julian-tf8nj]

I wish we had these videos when I took a Computational Theory graduate course, a good while back!!

[@lexinwonderland5741]

Thomas Kern is a favorite of mine, he first broke thru with #SoME2 and his video on Ehrenfeucht-Fraïssé games, and then his series of lectures on regular languages and finite automata has been really accessible imo, the guy obviously loves his field and teaching it and gives off the vibes of "medium-young professor who's so engrossed in his field he is detached from reality and doesn't even hate his job, gets way too carried away in 100s courses and scares half the students, but is everybody's favorite 400s/grad professor, but also probably forgets to sleep and eat regularly", the vibes are good

[@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.

[@danielyuan9862]

I believe you may be able to prove all of them. You just can't have an algorithm that can prove all of them.

[@overloader7900]

It is simply impossible to solve X for (X == !X)

[@NoLongerBreathedIn]

@@danielyuan9862 No. If every non-halting program had a proof it didn’t halt, there would be an algorithm to find said proof by brute force.

[@Warwipf]

There are some problems that can not be proven. Some of which might not even have a possible proof for their impossibility to prove. Let P be one of those problems: Does the algorithm while(P has a proof); halt?

[@wizard7314]

@@NoLongerBreathedIn That is logically unsound. You wanted to conclude B, so you just assert that A implies B. Lol.

[@BasteG0d69]

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! :-)

[@SuperFashi]

captured

[@yagomizuma2275]

What is a bs

[@achewy7700]

@@yagomizuma2275 bachelor of science, it's a type of 4-year degree

[@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!)

[@pvic6959]

I started college in 2015. I had my first exposure to the fascinating world of sorting algorithms in my first class. I wanted to learn more so I started watching videos of sorting algorithms and found this channel. The way it was presented was so unique i HAD to subscribe and I am so happy I did. it really is a pleasure when a new upload happens!

[@wombatZ]

These videos are incredible. It would have been amazing, if I had found the channel earlier :D Great explanation and most importantely, difficult stuff is explained correctly in a simple manner. Most channels skip the difficult part and spend 15 minutes explaining the "easier" stuff.

[@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 KZbin till now. Keep it up! I really want to see the next TBA videos... :)

[@Irondragon1945]

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

[@theopantamis9184]

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 !

[@mikicerise6250]

Oh, I don't. I know these kinds of videos are an absolute game changer, especially for those of us who want to learn and study but do not have the financial means for traditional schooling. KZbin has democratized scientific knowledge more than anything else in the past few decades, which is why I still stick around, despite its flaws.

[@McMurchie]

This is multiple lifetimes of knowledge in 20 minutes.

[@zacw8869]

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!

[@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.

[@nagoshi01]

This is amazing. PLEASE make more videos like this. I love learning about complexity spaces

[@insidetrip101]

So cool this channel still makes videos. I watched the halting problem video so many years ago.

[@shinqqing5161]

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!

[@markwarburton8563]

I love your more practical approach to describing these complex topics. Thanks!

[@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...

[@AntoniGawlikowski]

I love the clarity of the explanations. Chapeau bas!

[@CyberAnalyzer]

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

[@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.

[@GimmeMyHandleBack]

Yooooo these guys again. I love y’all’s videos, even if I can’t understand one or two of them

[@UCFc1XDsWoHaZmXom2KVxvuA]

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?

[@udiprod]

Thanks! My formal training is in computer science. I keep learning too from various sources, books, lectures, papers, and so on. So I can't point to one source in particular. Thanks again :)

[@dreftymac9916]

since you were asking for a book, en.wikipedia.org/wiki/G%C3%B6del%2C_Escher%2C_Bach Godel Escher Bach by Hofstadter ... even though you did not ask me *shrug*

[@sychuan3729]

I'd recommend Scot Aaronson's "Quantum computing since Democritus". It is very good

[@UCFc1XDsWoHaZmXom2KVxvuA]

@@dreftymac9916 Geb is marvelous, it changed my life when i read it about a year ago!!

[@sichel94sam]

Thank you for making really easy examples along the way! Keep it up

[@kavalkid1]

Marvelous! Thank you! I so enjoy exercising my mind.

[@cortster12]

A scifi book I read did something like this, but with time travel instead of quantum entanglement. Basically, they sent the result back in time, and then kept analyzing it, over and over again forever. In effect, the result was instant. So it was a computer that instantly outputted no matter what was input, purely through time travel.

[@Julian-tf8nj]

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?)

[@12-343]

I think it's something along the lines of "you can't set which value it will be, but you know it will be the same for both", so it's like having the same seeded random number generator.

[@NoNTr1v1aL]

They uploaded again! Hallelujah!

[@israelRaizer]

wait, there's a whole team of people behind udiprod?

[@israelRaizer]

@Google user oh right, english is not my first language, singular they is still a weird thing for me

[@isabelmorel2225]

this is the BEST youtube of all times!!!!!!!!!!!!!!!!!!!!!!!!!!!! just so beautiful!!!!!

[@mrosskne]

with your visual aids and your skill in explanation, I was able to keep up almost to the 2/3 point

[@dalegillman5287]

Thank you for uploading this. 😃

[@imserdar]

You guys are the best!!!

[@bwill325]

Beautifully clear and detailed. Very nice video.

[@codegeek98]

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

[@azertycraftgaming]

Wow I discovered your channel today and there already is a new video!

[@azertycraftgaming]

Ok that's a lie, I had seen the synchronisation problem already

[@wrong1029]

Where were you when I was taking Formal Language & Automata. This is incredible.

[@awpbaldyMC]

my favorite youtube channel

[@alfonsopayra]

this channel is amazing

[@kylechin8706]

Intro on point, I'm stealing that and using it for everything. "X happened and this media is about that."

[@legendgames128]

5:06 for every unique input, a number called w, there are 2^w ways to toss true/false at it. There can be repetitions, so the number of inputs at all is n. For every input, there is a logical operator between them. 2^(n-1) in fact. For every input, n, you can invert it. So 2^n ways to set up inverters. The parenthesis. For every input n, there are (n choose 2)-1 ways to place one set of parenthesis. p is parenthesis, and for every set of parenthesis in the formula, there are (n choose 2)-(p+1) ways to put new parenthesis in the formula.

[@legendgames128]

All together that's 2^(w+2n-1)*((n choose 2) - (p+1)) ways to set up a Boolean formula.

[@LydellAaron]

Thank you for this fantastic video explaining this topic.

[@meloncat1997]

I am hoping this will be explained in one of the future videos, I can follow the entire video except the very beginning of part 5. With regular MIP, honest provers will always produce the exact same answer, while dishonest provers guess and have a high probability of failure, got it. With MIP* what happens is that dishonest provers can coordinate and coordinate identical wrong answers with high probability given enough entanglement nodes, also got it. Then, I think, what the video is saying that: honest MIP* provers require some N amount of entanglement nodes to prove that program W will halt (I am assuming they both have to tell the verifier how many cycles the program will take to halt and it checks if its the same answer), but why would honest provers need nodes for coordination? Or am I misunderstanding the video? Assuming we're working with honest provers, wouldn't this magical machine be functionally equivalent to a pair of them entangled or not? Exactly like how singular honest prover in IP is equivalent to a pair of them in MIP. Otherwise great video and I cautiously might try to dig into this on my own.

[@udiprod]

Generally speaking, the verifier gives the provers a computational test that can only be passed if the word w is in L. For example, in the non-isomorphic graphs case, the test is to detect which graph it is, and it can only be done if the graphs are not isomorphic. In MIP* the quantum entanglement allows to provers to coordinate their answers, but more generally it allows them to cooperate in new, non-classical ways. For the halting problem, the test that the verifier gives the provers is a such that the provers can pass the test only if two conditions are satisfied: a) They cooperate in non-classical ways using the entanglement. b) The input program halts. Condition (a) is important. If it wasn't there, this test could have been used with MIP games, but we know that MIP can't handle the halting problem. Now let's see what happens if this test is given to a single prover in an IP game. An honest prover would simulate two honest provers that cooperate via the entanglement. A malicious prover would cheat: it would simulate two provers that communicate freely. This is more powerful than entanglement. This extra power will allow it to pass this test for input programs that doesn't halt, violating (b), and the soundness requirement.

[@meloncat1997]

@@udiprod with those conditions in mind and clarification, I understand it now, thank you! The exact mechanics are still lost on me, but I'll trust that it can only be simplified so much, especially in pop-sci animation format and a youtube comment. It's also literal quantum mechanics so I don't feel bad about not fully understanding them...

[@kindlin]

​@@udiprod Thank you for this video, but thing the that makes no sense to me, is how can entanglement help anyone, solver or verifier? It's impossible to transmit information through entanglement, as correlating results via classical means is the only way you can even know something is entangled, so how can them being entangled help with coordinating (transmitting knowledge) in any way? It must have something to do with the initial discussion, prior to the tests being ran, but again, they can't say they'll measure some amount, or anything, about the entangled particles to help them, because they can only verify the particles were correlated at all once the test is complete and they can compare answers, classically, once more.

[@kindlin]

@@meloncat1997 I just read this entire section: en.wikipedia.org/wiki/Quantum_pseudo-telepathy#The_Mermin%E2%80%93Peres_magic_square_game And it makes a tiny bit more sense, but I still don't see the Mermin-Peres magic square helps anything. Each person still measures a particle and each particle's result is still random. They only ever even know they had entangled particles when they come together and can classically compare their results. The key must be the different "basis" discussed in that section, as they claim the important part is that Alice checks, for example, the Z and X basis for her states, allowing her to identify a coordinate in her square to be filled in, but I'm totally lost here. The basis must be something different from just X or Y directions like for spin, it must be some other fundamental mathematical object, though I suspect I need a math or physics degree (engineering isn't cutting it) to actually understand this.

[@udiprod]

@@kindlin Thanks! Though it's a bit non-intuitive, it turns out it's possible to coordinate without transmitting information. The Wikipedia article you mentioned is just such an example: Alice and Bob can win a game they would otherwise lose, and they don't transmit information.

[@MatthewFearnley]

Nice! I think I learned quite a bit before my brain gave out. Maybe I'll give it another try later. It might be nice to see a more concrete example (if possible?) of how the malicious provers use those clicky green things to communicate^Wcoordinate.

[@fitness60plus52]

astonishingly clear

[@mrgamercooldude546]

They’re BACK!

[@lolatomroflsinnlos]

16:35 Instead of entangled particles, what about this strategy: The provers agree on a random seed and use that to generate random answers, ensuring they both give the same sequence of answers. This should work unless the verifier asks different questions . But asking different questions would also throw off the strategy with entangled particles. So what is the difference between those two strategies that makes the provers with entangled particles more powerful?

[@qanon4realvsqanon4gery70]

The short answer is that the veirfier can ask different questions and that entangled particles can be used to strategise against that. To understand how will take some reading on the subject.

[@Jcarr250]

My understanding is that the strategy with entangled particles isn't a simple one. They don't use it to answer questions directly, but to query certain faked "properties" about the whole space. And the meaning of the particles is fixed ahead of time regardless of the questions from the verifier. Imagine the verifier asks you `Left` or `Right`, and you have to answer 1 or 0 and pick the same number as your partner if it was the same Left/Right. Ignoring the trivial constant strategies, the queries you get from the entangled would be checking the spin in one dimension for Left, or another for Right.

[@deinauge7894]

they don't have to use the entangled pairs in sequence. with n particles for each solver, there is a n-dimensional space of entangled quantities that can be measured, and the choice what quantity is measured by which machine can depend on the queries. they will in general not be the same. as an example, say we have two particles of spin 1/2. if solver 1 measures the spin of particle 1, but solver 2 measures the sum of the spins, than their answers are correlated, but in a different way than if they use a fixed sequence of numbers.

[@Jcarr250]

@@AndreaPassagliaAP Because the answers they give have to be dependent on the questions from the verifier, and yet coordinated. That's the key insight. They don't know ahead of time what they have to respond to, and they can't communicate, but they need their answers to agree regardless of what the verifier asks about. With very very simple examples like these they're too simple to be able to have quantum strategies that help. Here's a slightly bigger game which does have a quantum strategy: en.wikipedia.org/wiki/Quantum_pseudo-telepathy#The_Mermin%E2%80%93Peres_magic_square_game For that game, any strategy where they coordinate ahead of time has to result in a mistake 1/9th of the time at least, but it's possible to use the correlation from quantum entanglement to get 100% accuracy using an entangled particle pair.

[@jeanf6295]

I guess this is related to quantum contextuality and quantum pseudo telepathy (en.wikipedia.org/wiki/Quantum_contextuality , en.wikipedia.org/wiki/Quantum_pseudo-telepathy ).

[@taiyihanle]

I've gotten lost about the meaning of a 'language' as used in the video, and now am pitifully jumping between chapters in hopes of finding the short part where this is mentioned, so I can progress up to the point of understanding such a breakthrough that was made--- but in a way that I don't rewatch everything entirely, because I cannot admit not having understood what I already watched. ]:

[@taiyihanle]

0:39

[@lolatomroflsinnlos]

A language (or formal language) is a subset of all words given an alphabet. The alphabet might be {0, 1}, then the set of all words would be all strings consisting only of 0s and 1s. A language might be the set of all words, or the set of all words only containing a 0, or the set of all words that represent an even binary number, etc.

[@acasualviewer5861]

@@tissuepaper9962 a "set" is a more general concept than a "language".. in theoretical computer science a "language" is a set with very specific constraints. For example that it contains words formed with a given alphabet.

[@LlemonDuck]

@@tissuepaper9962 All languages are sets, but not all sets are languages :) This is not a unique separation from the term "set" to computer science, either. Much of higher abstract mathematics goes on to define more objects with higher specificity than sets, such as groups, fields, rings, topologies, etc. While it is entirely possible to consider the set-like properties of such an object, we need these further distinctions in order to build meaningful conclusions from them.

[@tissuepaper9962]

@@LlemonDuck and which special property of languages was necessary for this problem? My point was that it was needlessly specific, and clearly confusing if this comment is any indication.

[@tanchienhao]

Amazing video!!!

[@GreatFernicus]

Never did I think I’d see quantum entanglement brought up in a computation theory context

[@ANSIcode]

16:55 "because of the entanglement, this has an immediate effect on a particle of the other prover" this is either a misrepresentation of what entanglement is, or using the word "effect" with a very non-standard meaning. While I assume the video author knows it, this is a common misconception about entanglement and the video may further spread it. When an event X "has an effect" on a thing Y, it is commonly understood that you can tell whether X happened by looking at Y. This is not the case with entanglement. For example, in the situation at 16:55, the other prover has no way of telling whether the first prover performed any measurement or not. Measuring entangled systems cannot be used for communication.

[@SomeRandomFellow]

While I am no expert on quantum entanglement, I believe the intended meaning was "Measurement X was made by Prover A, and due to the entanglement measurement Y must be made by Prover B". Of course, measurement Y can still be made by Prover B without Prover A first making measurement X, so Prover B has no way of knowing that measurement X was taken.

[@cacophony435]

When you brought up Not-Halt, my head started spinning.

[@byronwatkins2565]

That is very clever! (And reminiscent of thermodynamics.)

[@Ariana-dn4mm]

4:45 huh i thought cvp was not in p other than that wonderful presentation that's hopefully accessible to a wider audience!

[@rebluecrow]

Great explanation.

[@snipebuddy]

underrated indeed!

[@SilverWolf340]

I just graduated high school having taken nothing past physics 1 and yet I watched this entire thing, understanding maybe a third of it

[@schmetterling4477]

Sure, kiddo, sure. ;-)

[@codahighland]

It wasn't relevant to the story, but a fun bit of trivia: While NP > P and NEXP > EXP are probably true, we actually have a proof that NPSPACE=PSPACE.

[@anselmschueler]

I have a question: When you talk about the simulation of the MIP* verifier-prover interaction, you say that increasing the amount of entanglement dimensions leading to the verifier accepting the proofs means that the proof was correct. But this isn’t a requirement for the verifier, right? Couldn’t it also be that the verifier simply only works up to some amount of dimensions, after which the malicious provers are able to trick it? Or is the class defined such that the verifier must work for all amounts (excluding ∞) of dimensions? Or is this always the case, and it’s impossible to trick the verifier consistently, regardless of the amount of dimensions? I don’t think this is clear.

[@udiprod]

Right, the latter. The provers are defined to have a finite, though arbitrarily large number of dimensions. The completeness requirement says that for an input w in L, then with a sufficiently large number of dimensions they can convince the verifier. The soundness requirement says that for w that is not in L, they can't convince the verifier (with high probability) no matter how many dimensions they have (excluding inf).

[@anselmschueler]

@@udiprod I see, that makes sense, although it makes it even less intuitive that this would increase the amount of problems that can be verified. Thanks!

[@andrewporter1868]

Upon scrutinizing the halting problem theorem, I am convinced of the opposite: HALT \in R. Discussion requested.

[@smokeydops]

I get where we were at at part 5 now... basically, MIP* is the big discovery, that quantum probability can be used to get satisfactory probability for solving if a program halts. But, there are models of quantum entanglement that differ from one another. I think that means that despite our best efforts, HALT does not have a deterministic solution or a deterministic proof; it can only be probably solved in an probable amount of time. (because the infinite entanglement can always find a way to fool the verifier, and limited entanglement cannot) Is that right? I wonder if that means the universe is not logically deterministic...

[@HopDodge]

For the satisfiable boolean formulas the output space needs to include both true and false correct? Just making sure that something like A||!A doesn't pass.

[@htomerif]

Its quite simple: infinite dimensional entanglement can't be approximated by the finite tensor product model. I gotta say, you really Frog Fractioned the hell out of this explanation.

[@schmetterling4477]

Neither does it exist. Mathematicians simply don't understand physics. Never have, never will. ;-)

[@Renecromancer]

“The machine will run forever and get stuck.” *RAID shadow legends ad starts playing*

[@cmilkau]

Amazing explanation. But the really new and interesting part falls a bit short. How can the verifier turn the tables? Why does this verify all of RE?

[@kingkonefpv4553]

Does a fuzzy logic verifier also count into more powerful verifiers?

[@ashlandwithouttheshd]

In my algorithms class 10 years ago, when I first heard about complexity classes, I figured I would eventually understand this concept after reading about it a few more times. After having it explained to me over 100 times now, I can safely say I’m just too dumb to understand complexity classes.

[@ichigo_nyanko]

imagine a program which takes n and goes through a for loop: for i < n: //do something this complexity class is O(n) because as n increases, the amount of time it takes also increases the same amount. You can see this just by counting the number of operations the program is doing. When n is 15. it goes through the for loop 15 times. When n is 50 it goes through 50 times. Now if you imagine this program for i < n: for j < n: /do something If you count the number operations it does for any n. you will see that it finishes the program after n^2 operations. For example when n = 2. i=1, then j loops 2 times, then i=2, and j loops 2 times. As you can see you pass the 'do something' line 4 times. (which is n^2=2^2). So this program has complexity n^2 Basically, the complexity class is just how many operations the computer would do given some input.

[@ashlandwithouttheshd]

I appreciate your effort, but Big O notation is a different concept than complexity classes. I understand Big O. I don’t understand complexity classes.

[@ichigo_nyanko]

@@ashlandwithouttheshd Sorry for my bad explanation. While they are not the same concept they do measure similar things in very different ways. The complexity class as I understand it is just the type of function in big O notation. In both of my examples O(n) and O(n^2) would be in P. a solution to a problem with O(2^n) would be in EXP. I'm not an expert on this area of mathematics (I do category theory and related stuff like topology) but this is my understanding. Please correct me if that is wrong. edit: after some very very quick research on wikipedia it seems like the complexity class is what I stated above plus a language and a computation model. i.e. it is the constraint on resources (written in big O notation), the language, and the computation model. The most important part of the class is still how efficient it is of course - and again that is the type of function in big O.

[@rexor8527]

I like your funny words magic man!

[@killerkonnat]

I really want to know how MIP* is advantageous to the verifier, no having it explained even slightly left me confused.

[@Bry10022]

Do SMP codepoints and emoji count as more than one character to the verifier?

[@bennetteidsness3275]

I'm curious: do we actually have that HALT verifier for the MIP* scenario? I mean, it's possible that the two models WOULD converge, but it's impossible to produce the verifier, which means that we can't actually produce the semi-solvers that are necessary to combine into the full solver. Wouldn't that also avoid solving the halting problem?

[@udiprod]

You are right, but this was the situation prior to 2020. We didn't know back then if a halting verifier exists, and we didn't know if the models converge. The 2020 discovery was the halting verifier algorithm for MIP*. Since we now know it exists, we conclude that the only thing that can prevent solving the halting problems is that the two models won't converge.

[@Artikash]

Did we need this result to solve Tsirelson's problem? There was apparently an earlier result that NEEXP is in MIP*. The machine at 22:15 seems to run in polynomial space, so if it works it would mean NEEXP is in PSPACE, which I presume can be easily shown to not be the case. QED?

[@realcygnus]

Nice ! Heavy Duty 👍

[@gnpar]

Amazing

[@Chloe-ju7jp]

New udiprod upload lets goo

[@Bluedragon2513]

For MIP*, if both questions are not equivalent, why are they answering according to how the quantum entangled information is shown?

[@alessandrorossi1294]

What is a good textbook about this material? I love it

[@Verrisin]

(a python script _with very limited IO_ - there must be predetermined/no input and output must never block ;; the input includes all platform information, etc.)

[@i_teleported_bread7404]

Oh hey, udiprod is back

[@onemediuminmotion]

*'Separation in space' **_is_** 'separation in time.'.* Not only is [_my_ use of] this statement a reference to the fact that it takes "time" for 'light' to "traverse" ['propagate through'/'produce the sensory-awareness waveform image of'] the '"intervening space"' between any two {"separate"} mass objects, it also refers to the fact that each 'separate unique individual' 'particulate mass-object' is 'physically defined/manifested' *_as such_* by [means and in terms of] the unique series-sequence[-additive combination] of light (EMR) waves impinging upon it [_as_ "it"] during the course of its "existence" as a _specific_ [distinct and distinguishable as such] 'spacetime event'. This 'ability' of the universal-BH to 'manifest' its CPS ('center-point singularity') as/at 'many different particle-locations in space' at 'the same time'/'simultaneously' isn't a physical 'paradox', but rather a 'physical necessity' in order for it to 'manifest' "the [history of the] universe as we see [and otherwise 'experience'] it" _as such_. See also, and carefully digest, my comment at "What is a Worldview" (kzbin.info/www/bejne/d4eknoxnfdt4rqs). Thanks.

[@karlgiese6100]

I like your funny words, magic man

[@Julio974]

"Using the entanglement: TBA in a few weeks" wait, really?!

[@matthewgrange9310]

Very cool

[@danielchin1259]

Cool vid.

[@lacasadeacero]

i like all the visual components.

[@ukpoetry]

Global temperature modelling and mRNA technology is ExpHard, right?

[@tezlashock]

Doesn't that make the Commuting Operator Model a Halting solver too and therefore does not exist either? It would make sense considering it requires infinite dimensions of entanglement to be achievable

[@ChurchOfThought]

Infinite correlation is akin to what? 🤔

[@pineapplewhatever5906]

4:10 Isn't there an algorithm proven to work in O(n^6)?

[@Google_Censored_Commenter]

This breakthrough is insane. With the power of RE, couldn't we solve the famous n = np problem very easily, since it's inside RE?

[@cubing7276]

RE problems halt eventually when the answer is yes, but that only proved that you can have an algorithm that can verify RE solutions, not solve them That is given the proof we can easily check it's correct or not, but we don't have a proof

[@feritperliare2890]

Somehow I'm not sure when my head hurt more before I understood what some of this stuff meant or after there is clearly some time gap but goddamn it feels both satisfying and painful

[@steventinsley2396]

I've watched this and another video about this discovery and one thing that isn't clear to me is what these all powerful provers actually are. They seem to be like oracle machines, although how an imaginary machine that couldn't really be built can help one verify proofs of a real problem is also an open question.

[@maxthexpfarmer3957]

How does the computer simulate computers with infinite dimensions?

[@legendgames128]

A Not-Halt pseudo-semi-solver: halts if no, goes on if yes.

[@Jesse_Carl]

Wow, way over my head, but very cool. I'll definitely take some classes on this in a few years

[@Jesse_Carl]

I'd like to report back, I have taken the classes, and it is no longer over my head. Still very cool though.

[@legendgames128]

2:38 not Boolean satisfactory unless you account of the little delay that happens when switching from true to false. That's the basis of a clock

[@raunaquepatra3966]

How is prime solver P, were is this coming from? 🤔🤔 Any links would have been great

[@MateusAntonioBittencourt]

I understood 12% of this video.

[@TheRomichou]

I understood more in 24 minutes than in the many hours reading and listening to boring lectures...

[@nickikallman390]

10:31 are there not exponentially, not polynomially, many possible inputs? Or am I missing something?

[@udiprod]

Yes, there are exponentially many inputs, and the simulation takes an exponential amount of time. But it takes only a polynomial amount of space, since every iteration takes a polynomial space, and then you can clear it and re-use it for the next iteration. So the simulation machine is in PSPACE, which is what we intended to prove (NP is contained in PSPACE)

[@underrated1524]

It just occurred to me that there is one really important implication of MIP*=RE. I have heard it said that in terms of computer security, if it turns out that P=NP, then all hell breaks loose, because having problems that are hard to solve but easy to verify is crucial for security. But this gives us an out even in that situation - somewhere we can turn to, such that we can continue to be secure even if P=NP.

[@underrated1524]

Hi, past me. I'll just comment that MIP serves the same purpose, and is probably easier to use in practice than MIP*.

[@magicmulder]

P=NP may still not end encryption as we know it as the proof may be so abstract that we can’t deduce a polynomial algorithm from it. Or we get a polynomial algorithm that is terrible in practice, like O(n^500,000 ).