@@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.
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!
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
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?
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 !
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. TH-cam has democratized scientific knowledge more than anything else in the past few decades, which is why I still stick around, despite its flaws.
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 TH-cam till now. Keep it up! I really want to see the next TBA videos... :)
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!
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.
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...
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!
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.
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!
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?)
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.
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?
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 :)
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*
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.
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.
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.
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?
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.
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.
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.
@@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.
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 ).
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.
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.
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.
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.
@@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...
@@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.
@@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.
@@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.
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. ]:
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.
@@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.
@@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.
@@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.
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.
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)
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.
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.
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.
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.
@@aperson1234-t8x 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.
*'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" (th-cam.com/video/AVAmY1HvExI/w-d-xo.html). Thanks.
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...
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?
Gotta say, this is by far the most lost I've felt in a long time when it comes to all this weird computation problem type stuff. Part of that is unavoidable with the exceeding amount of layers upon layers this sorta explanation has to pile up in a row. But also it feels like the deeper into the layered machines and omniscient malicious robots the video goes, instead of giving more time and examples for why something is true, it just starts stating increasingly complex things with no elaboration before building the next part of the video on that assumption. Like at 16:20 the argument of "interrogate them to find contradictions means more power" makes sense, but a little bit more elaboration with an example of a problem that can only be efficiently solved this way would have helped it sink in, as was done for the earlier steps. Then at 16:40 we introduce the idea of giving the provers entangled particles to coordinate their lies. But we still have no clue what coordination even really means between them, let alone how they could possibly turn that into a coordinated system of changing their response to unknown questions with polynomial possible responses. Then by 17:40 with no understanding of the coordination between provers, or how the provers would use entangled particles to coordinate; With no elaboration it's also then just asserted that there is a way to turn it around and the verifier is even stronger now. Even in the comments and description clarification for this specific part, the explanation seems to be just "Well it gives them a challenge that works out that way" And that's before we get to "Now set up an orange box that could simulate every possible strategy the omniscient provers could use to pretend to solve an uncomputable problem using arbitrarily many entangled particles to fool an infinitely clever computer trying to pit them against each other. Clearly you can see that this simulation will converge to .3% accuracy with 10 qubits." Like, I'm sure there's a very good reason there isn't in depth explanation at this point. It *is* cutting edge theoretical quantum complexity theory or whatever. Just the video seems to treat it like we're still taking small natural steps in the progression of this argument that need no further elaboration when a "I don't have the time to justify this specific assertion but check this source for more detail on this step if you're interested" would probably have helped the flow for a lot of people. All that said, it's still extremely fascinating and probably about as well presented as this sort of topic can be. Dunno how I didn't find this channel sooner but definitely am subscribing, keep up the good work!
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?
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.
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.
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).
@@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!
(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'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.
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
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.
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 ).
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.
I still don't understand how the provers lose power when they are allowed to use entanglement. Can't they just always not use the extra power and be at least as good at fooling the verifier as before?
The verifier forces them to use the entangelement. 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, but then it was discovered that there exists such a challenge that the provers can only win when an input program halts. But winning this game requires using the entanglement, or else it was doable already with MIP.
@@udiprod so in reality the provers gain power but it's not a problem because the challenges are designed in a way that only the benign provers benefit from the entanglement. It's not very clear in the video since the verifier can't force the malicious provers to not play dumb
Imagine NRE, things that when verifying, if it is correct, it will stop, but if not, it may run forever. What about stuff outside NRE? Is there anything outside NRE?
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
It's common notation in logic. Wikipedia describes the history of these symbols: en.wikipedia.org/wiki/Logical_connective#History_of_notations The ||, &&, ! symbols have a separate history coming from usage in computer languages (possibly due to available characters constraints).
I don't understand how equipping the provers with entangled particles can help the verifier. Worst case they should just completely ignore their particles, assuming they are malicious and know that using them will help the prover. Are they forced to use the particles or something?
Yes, your deduction is correct: they are forced to use it. Think of the non-isomporphism example: the verifier gives the prover a computational challenge, such that the prover can only succeed in it of the graphs are non-isomorphic. The entanglement allows the provers to succeed in a wider range of computational challenges. This offers new oppurtunities for the verifier, as there are now new challenges it can ask the provers, but it's not at all obvious if this allows for any useful ones. The recent 2020 discovery found that there exists a computational challenge related to the halting problem, such that the provers can only succed by using the entanglement, and if the input program halts.
I think things were going well and reasonably explained to an enthusiast until ~ 15:30 Going forward there was a lot of handwaving, which kind of make the video less informative, as we only get a very superficial notion of what is happening, not a fleshed out explanation
My heart stopped for a second when the halting solver appeared but then I realized the implication a millisecond later and was very relieved
Same here, lol !!!
"HEYYYYY HEYYYY HE- ohhhhh"
same
+me
Why
It was quite a shock when the malicious provers walked to meet each other.
Look how lively they’re animated.
I also found it quite jarring hahaha
bigger shock that particle can be sent through the wall and it is not considered a communication :-D
@@luckabuse No particle is ever sent through a wall. Two particles are entangled.
@@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.
16:00 - As an animator, I find those malicious provers adorable! Very nicely done! Simple, and yet you conveyed the emotions perfectly! Love it!
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!
I wish we had these videos when I took a Computational Theory graduate course, a good while back!!
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
To anyone who thinks you can't prove that a program doesn't halt: you can. You just can't prove all of them.
I believe you may be able to prove all of them. You just can't have an algorithm that can prove all of them.
It is simply impossible to solve X for (X == !X)
@@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.
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?
@@NoLongerBreathedIn That is logically unsound. You wanted to conclude B, so you just assert that A implies B. Lol.
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! :-)
captured
What is a bs
@@yagomizuma2275 bachelor of science, it's a type of 4-year degree
BoS sounds way better.
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 !
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. TH-cam has democratized scientific knowledge more than anything else in the past few decades, which is why I still stick around, despite its flaws.
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 TH-cam till now. Keep it up! I really want to see the next TBA videos... :)
This was a beautiful watch. The voice, the animations, the pacing, the topic.
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!)
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!
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.
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...
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!
What a time to be alive; this is terrifying that we're able to reason so much about _what can be figured_
This is multiple lifetimes of knowledge in 20 minutes.
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.
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!
So cool this channel still makes videos. I watched the halting problem video so many years ago.
I cannot wait for the video about quantum entanglement! Why it isn't possible to communicate with it is extremely fascinating!
Yooooo these guys again. I love y’all’s videos, even if I can’t understand one or two of them
this is the BEST youtube of all times!!!!!!!!!!!!!!!!!!!!!!!!!!!!
just so beautiful!!!!!
This is amazing. PLEASE make more videos like this. I love learning about complexity spaces
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?)
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.
I love the clarity of the explanations. Chapeau bas!
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?
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 :)
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*
I'd recommend Scot Aaronson's "Quantum computing since Democritus". It is very good
@@dreftymac9916 Geb is marvelous, it changed my life when i read it about a year ago!!
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.
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.
I love your more practical approach to describing these complex topics. Thanks!
with your visual aids and your skill in explanation, I was able to keep up almost to the 2/3 point
Intro on point, I'm stealing that and using it for everything.
"X happened and this media is about that."
They uploaded again! Hallelujah!
wait, there's a whole team of people behind udiprod?
@Google user oh right, english is not my first language, singular they is still a weird thing for me
Where were you when I was taking Formal Language & Automata. This is incredible.
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.
All together that's 2^(w+2n-1)*((n choose 2) - (p+1)) ways to set up a Boolean formula.
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?
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.
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.
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.
@@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.
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 ).
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.
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.
Never did I think I’d see quantum entanglement brought up in a computation theory context
I just graduated high school having taken nothing past physics 1 and yet I watched this entire thing, understanding maybe a third of it
Sure, kiddo, sure. ;-)
“The machine will run forever and get stuck.”
*RAID shadow legends ad starts playing*
Beautifully clear and detailed. Very nice video.
Thank you for making really easy examples along the way! Keep it up
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.
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.
@@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...
@@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.
@@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.
@@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.
Next video about "The missile knows where it is, because it knows where it isn't" :D
Wow I discovered your channel today and there already is a new video!
Ok that's a lie, I had seen the synchronisation problem already
A Not-Halt pseudo-semi-solver: halts if no, goes on if yes.
Marvelous! Thank you! I so enjoy exercising my mind.
When you brought up Not-Halt, my head started spinning.
6:30 What about python programs... that are supposed to be video games?
this channel is amazing
7:23 You can prove that a few programs do not halt.
The program shown keeps running the loop and has no condition to end the loop.
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.
]:
0:39
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.
@@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.
@@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.
@@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.
Thank you for uploading this. 😃
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.
Neither does it exist. Mathematicians simply don't understand physics. Never have, never will. ;-)
4:45 huh i thought cvp was not in p
other than that wonderful presentation that's hopefully accessible to a wider audience!
10:31 are there not exponentially, not polynomially, many possible inputs? Or am I missing something?
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)
my favorite youtube channel
4:10 Isn't there an algorithm proven to work in O(n^6)?
They’re BACK!
Thank you for this fantastic video explaining this topic.
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.
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.
You guys are the best!!!
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.
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.
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.
@@aperson1234-t8x 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.
*'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" (th-cam.com/video/AVAmY1HvExI/w-d-xo.html).
Thanks.
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...
Upon scrutinizing the halting problem theorem, I am convinced of the opposite: HALT \in R. Discussion requested.
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?
astonishingly clear
Gotta say, this is by far the most lost I've felt in a long time when it comes to all this weird computation problem type stuff. Part of that is unavoidable with the exceeding amount of layers upon layers this sorta explanation has to pile up in a row. But also it feels like the deeper into the layered machines and omniscient malicious robots the video goes, instead of giving more time and examples for why something is true, it just starts stating increasingly complex things with no elaboration before building the next part of the video on that assumption.
Like at 16:20 the argument of "interrogate them to find contradictions means more power" makes sense, but a little bit more elaboration with an example of a problem that can only be efficiently solved this way would have helped it sink in, as was done for the earlier steps.
Then at 16:40 we introduce the idea of giving the provers entangled particles to coordinate their lies. But we still have no clue what coordination even really means between them, let alone how they could possibly turn that into a coordinated system of changing their response to unknown questions with polynomial possible responses.
Then by 17:40 with no understanding of the coordination between provers, or how the provers would use entangled particles to coordinate; With no elaboration it's also then just asserted that there is a way to turn it around and the verifier is even stronger now. Even in the comments and description clarification for this specific part, the explanation seems to be just "Well it gives them a challenge that works out that way"
And that's before we get to "Now set up an orange box that could simulate every possible strategy the omniscient provers could use to pretend to solve an uncomputable problem using arbitrarily many entangled particles to fool an infinitely clever computer trying to pit them against each other. Clearly you can see that this simulation will converge to .3% accuracy with 10 qubits."
Like, I'm sure there's a very good reason there isn't in depth explanation at this point. It *is* cutting edge theoretical quantum complexity theory or whatever. Just the video seems to treat it like we're still taking small natural steps in the progression of this argument that need no further elaboration when a "I don't have the time to justify this specific assertion but check this source for more detail on this step if you're interested" would probably have helped the flow for a lot of people.
All that said, it's still extremely fascinating and probably about as well presented as this sort of topic can be. Dunno how I didn't find this channel sooner but definitely am subscribing, keep up the good work!
Ok but when do you ever get magical all mighty machines that sometimes turn malicious
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
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?
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.
I like your funny words magic man!
What is a good textbook about this material? I love it
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.
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).
@@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!
I really want to know how MIP* is advantageous to the verifier, no having it explained even slightly left me confused.
(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.)
underrated indeed!
“So for this next bit, yeah, we’re just gonna give the provers quantum devices.”
“Why?”
“Why not?”
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.
I like your funny words, magic man
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
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.
Hi, past me. I'll just comment that MIP serves the same purpose, and is probably easier to use in practice than MIP*.
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 ).
Global temperature modelling and mRNA technology is ExpHard, right?
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.
Oh hey, udiprod is back
I still don't understand how the provers lose power when they are allowed to use entanglement. Can't they just always not use the extra power and be at least as good at fooling the verifier as before?
The verifier forces them to use the entangelement.
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, but then it was discovered that there exists such a challenge that the provers can only win when an input program halts. But winning this game requires using the entanglement, or else it was doable already with MIP.
@@udiprod so in reality the provers gain power but it's not a problem because the challenges are designed in a way that only the benign provers benefit from the entanglement. It's not very clear in the video since the verifier can't force the malicious provers to not play dumb
Imagine NRE, things that when verifying, if it is correct, it will stop, but if not, it may run forever. What about stuff outside NRE? Is there anything outside NRE?
New udiprod upload lets goo
Do SMP codepoints and emoji count as more than one character to the verifier?
Does a fuzzy logic verifier also count into more powerful verifiers?
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?
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
Wow, way over my head, but very cool. I'll definitely take some classes on this in a few years
I'd like to report back, I have taken the classes, and it is no longer over my head. Still very cool though.
Why are the boolean operators different than || && ! etc ?
It's common notation in logic. Wikipedia describes the history of these symbols: en.wikipedia.org/wiki/Logical_connective#History_of_notations
The ||, &&, ! symbols have a separate history coming from usage in computer languages (possibly due to available characters constraints).
That is very clever! (And reminiscent of thermodynamics.)
Amazing video!!!
I understood more in 24 minutes than in the many hours reading and listening to boring lectures...
I don't understand how equipping the provers with entangled particles can help the verifier. Worst case they should just completely ignore their particles, assuming they are malicious and know that using them will help the prover. Are they forced to use the particles or something?
Yes, your deduction is correct: they are forced to use it.
Think of the non-isomporphism example: the verifier gives the prover a computational challenge, such that the prover can only succeed in it of the graphs are non-isomorphic.
The entanglement allows the provers to succeed in a wider range of computational challenges. This offers new oppurtunities for the verifier, as there are now new challenges it can ask the provers, but it's not at all obvious if this allows for any useful ones. The recent 2020 discovery found that there exists a computational challenge related to the halting problem, such that the provers can only succed by using the entanglement, and if the input program halts.
@@udiprod Yes that makes sense, thanks for breaking it down so nicely.
How is prime solver P, were is this coming from? 🤔🤔
Any links would have been great
I think things were going well and reasonably explained to an enthusiast until ~ 15:30
Going forward there was a lot of handwaving, which kind of make the video less informative, as we only get a very superficial notion of what is happening, not a fleshed out explanation
I agree - the later part seemed to speed up... when in fact it would have been ideal to sloooooow down!
Infinite correlation is akin to what? 🤔
5:22 Um, 2-SAT is in P.