Fermat's Last Theorem: th-cam.com/video/qiNcEguuFSA/w-d-xo.html Four Colour Map Theorem: th-cam.com/video/NgbK43jB4rQ/w-d-xo.html Gödel's Incompleteness Theorem: th-cam.com/video/O4ndIDcDSGc/w-d-xo.html P v NP: th-cam.com/video/dJUEkjxylBw/w-d-xo.html
His claim that every mathematical statement can be converted to a graph that is 3-colorable iff the statement is true is wrong. For example, given some formula in first-order logic (i.e. something like "for all x there exists y such that x does not equal y"), the statement "the formula is always true" cannot possibly always be converted to a graph. This is because the question of whether an arbitrary formula is always true is known to be undecideable - there is no algorithm which can determine the answer. If his claim were correct, we would have an algorithm: simply convert it to a graph and then check whether the graph is 3-colorable.
Ah, I see what you are doing. Just throw enough amazing content at us and we'll get distracted and go away. Well we aren't fooled so easily! We want to see the conversion of a mathematical statement (or two) into a 3-color map! :D
@@rosekunkel4317 So you're claiming that checking whether an arbitrary graph is 3-colorable _is_ decidable? Why is this so? I don't think the resulting graphs need to be finite.
Why do I get the feeling that he disproved his own statement with the example of the three countries in a triangle rounded by a 4th one? That is not possible to be three-coloring, but still a valid configuration. Or what am I not getting? /*edit*/ I made some drawings for myself and I can indeed color anything with in most cases 3 colors, but there are exceptions where I have to use 4. So if that is what is meant I find the name 'three-coloring' very confusing to use since it can be more. Maybe I'm just to logical as a computer-engineer.
I think the keywords to look for are SAT to 3-colorability. The steps in-between are turning a graph into a map, and turning a proof into a logic expression in the appropriate form.
You have two pens of different colours. You want to prove to your friend who is colour blind the pens are different colours without revealing the colours or anything else about the pens. You say hold one in each hand, put them behind your back, either switch or don’t. If I guess if you switched or not right once, either I guessed right, or the pens are different in some discernible way to me, the prover. Ie The chance I was telling the truth about there being a difference in the pens is 50%. If we do this game twice, 75%, 3, 87.5%, and so on until you’re sure enough the pens are different. The key here is I’ve proven the pens are different to you without revealing anything about them. This is very valuable in cryptography
@@rogerr4220 The basic concept isn't difficult to get. In less precise language, you're basically proving to someone that the proof (of some problem or the other) you claim to have is legit, without actually revealing the proof itself. To use a poker analogy (this is really imprecise mind), it'd sorta be like convincing everyone at the table that your hand is the winner, without actually showing your cards. How you'd do that in poker is beyond me, but the effect is the same - they believe you, despite not actually knowing what you've got.
@@ObjectsInMotion Ah, too advanced then for Numberphile's TH-cam audience? I tend to think not. Just list the educational dependencies up front. No need to cover them in their entirety in the video.
From messing around on paper and reading a bit: You start with a palette of F, T, and B. This palette is just a triangle of nodes. Whatever F is colored as means false. Whatever T is colored as means true. B is an auxiliary node. You enforce the law of noncontradiction by connecting to B. You encode a premise by connecting it to both B and F. This forces it to be true. You encode a negation ~X by connecting it to both B and X. You encode "X or Y" with another triangle. One of the nodes of the triangle is T. Another node is connected to X. Another node is connected to Y. The nodes that aren't T must be either BF or FB. X - B - F - Y or X - F - B - Y If X is F it forces the connected node to be B. F - B - F - Y And this forces Y to be T. F - B - F - T This works symmetrically. You can construct any statement in propositional calculus from or and negation. This means you can encode any Boolean satisfiability problem. I'm not sure where to go from there.
I don't think I've ever understood any concept less in my life, but I still really enjoyed listening to Avi, and it's always interesting to see these complex mathematical ideas, even if they make my head hurt.
"I can prove X" -> "I know what keys open that door" Whether X is true or false-> Whether the door opens or not The mapping of the proof -> The key Any statement can be a key, Only true statements/proofs open the door, however Party B does not know the internal mechanisms nor the keyshape. Party A has knowledge of the proof, can prove they have this knowledge by correctly identifying keys that open the door. They know whether the proof/statement they made is true and can be said to know the internal mechanisms. Three parts make it zero knowledge. Completeness (Party B will be convinced that Party A has proof, the probability of Party A picking correctly approaches 100% ), Soundness (Party A cannot cheat if they do not have the proof/The probably of Party A picking correctly gets closer to 0% if the statement is false), and Zero-knowledge. What makes it zero-knowledge is that Party B cannot look at the key. Party A looks at the key, Party B checks whether Party A picked correctly. This process is repeated, since it is 50/50 for the first time and it gets progressively more unlikely that Party A is guessing as Party A correctly identifies valid keys. The mapping is more like: The lock is the proof, the keys are the various different mappings, only true proofs have keys that open it. Both Party A and Party B can know how keys are made, but not necessarily how the lock functions. Since the method of key-making is known, you can't make false keys and there is no guessing.
In less precise language, you're basically proving to someone that the proof (of some problem or the other) you claim to have is legit, without actually revealing the proof itself. To use a poker analogy (this is really imprecise mind), it'd sorta be like convincing everyone at the table that your hand is the winner, without actually showing your cards. How you'd go about doing that in poker is beyond me, but the effect is the same - they have to believe you, despite not actually knowing what you've got.
@@ArawnOfAnnwn "How you'd go about doing that in poker is beyond me," why would you pick an example of which you don't know how to prove it? the whole point is knowing a way if how to do that...
@@sofia.eris.bauhaus "I don't think I've ever understood any concept less" - I explained the concept. You can feel free to explain the mechanism if you feel up to it.
It's like proving that you know the password to a computer by hiding the keyboard from view and typing in the password. Anyone can see that you unlocked the computer, so you must know the password, but that doesn't help anyone else figure out what the password is. The only new information they have is that they know you've proven you know the password.
It would be extremely helpful to see how to convert even a trivial statement into a map, as well as how to convert a 3-coloring of that map into a proof of that statement. Or at least a link to some paper where that process is explained, searching online returns no clear explanation.
Like he said, it’s using only formal proofs with symbols only, and a map would be huge for even a simple statement, so you would not really be able to translate it by hand or be able to comprehended if made by a computer. However, computers can communicate with each other in this language.
If I'm not mistaken, it takes a lot of definitions and tools, for example it probably goes through SAT and then through 3SAT to go to graph (map) colouring
@@TheKikou18 yes. Basically, no matter what branch of mathematics your statement is in, if first needs to be converted to pure logic. Even concepts as elementary as counting numbers and arithmetic are notoriously laborious to translate in this way (as evidenced e.g. by the lengths Whitehead and Russell had to go to just to show 1+1=2). I can scarcely imagine how hard it would be to encode concepts like arbitrary triangles in Euclidean geometry in this language.
@@varunachar87 I mean he said in the video that it can be explained even to a high school class, so I think that it would be an appropriate topic for Numberphile - there must be some explanation in between "its true" and "here's how to do it all out by hand."
Unfortunately in general, these maps will be absolutely huge, even for the most simple proofs because the conversion consists of several steps (proof → formal proof → proof-checking turing machine → boolean expression in CNF → graph → planar graph). Every one of them will most likely turn its input into an even bigger output.
@@waldtrautwald8499 Are there pure logic statements that would produce graphs/maps that are small enough to understand? Something like 1≠0? Or 0∈ {0,1,2}?
@@iveharzing You want a (somewhat short) boolean formula that is satisfiable iff your statement is true. This seems doable for your examples, depending on how you actually encode them. The size of the corresponding graph is then linear in the length of the boolean formula (in CNF). So the graphs shouldn't be too large. The key step is the reduction from SAT to 3-COLOR. There are some great visualizations online.
Knowing a property about a collection without knowing anything about the individual elements reminds me of quantum entanglement. I imagine there are interesting overlaps between NP completeness and quantum information theory.
To summarize: 1) you can show a map can be 3 colouring without revealing information about the colouring 2) you can transform any statement into a map 3) if that statement is true, you can do a 3-colouring on that resulting map C) you can do zero knowledge proofs for any statement
I am hoping that (3) is "If the statement is provable then you can do a 3-colouring on that resulting map", since otherwise this seems to conflict with Gõdel incompleteness.
@@anthonyberent4611 I'm not sure how Godel's factors into this at all? Eric's comment is perfectly correct. To be even clearer: 2) you can transform any statement into a map and any proof of the statement into a coloring of the same map.
@@anthonyberent4611 Only NP statement's can be turned into maps, the unprovable statements guaranteed by the incompleteness theorem all lie outside that set.
There are short statements whose shortest proofs are arbitrarily long (in any axiomatic system able to interpret basic arithmetic). To get a map of fixed finite size, you need a fixed finite bound on the length of proof that you'll accept. As for NP: "Statement X has a proof of length
@@RobinDSaunders So, are you saying that to create the map for a statement you need not just the statement, but also how large a proof you will accept for the statement? In that case, presumably, if the map you create is not three colourable, it doesn't tell you that there is no proof, simply that there is no proof shorter than your chosen N.
I love this, but I understand why its not on the main channel. Its not a bite-sized digestible chunk, but I think this sort of thing is fascinating and maybe its worth learning about seriously if I think so.
Honestly I wish this video h ad been on the main channel. This is one of the most profound numberphile videos I've seen; so much so that I've just spent half an hour trying to remember where I saw it to rewatch it.
This is way too awsome to be put on the second channel. Now I want to know, how a statement (even a very simple one) can be translated into a 3-coloring-map problem. Or is that also a zero knowledge thing?
the guy proving the existence of zero knowledge proofs was like: lemme prove that i have a proof that you can prove that you have a proof you don't want to tell
I am at the stage of dealing with proofs in my maths study. Some are like trying to wrap your head around a pole while singing opera and messing with a rubiks cube.
There are things I didn't understand at first but I think figured out : Say you have a map a and verifier that always pics the same country and ask to compare it to all the other ones, once the verifier has compared all the countries to the initial one, he will know for sure one of the colors. The verifier can then repeat the process with an other country with a different color from the first country, and he will the know for sure the exact three-coloring of the entire map. -> I guess this issue doesn't exist if you're only allowed to probe neighbouring countries. And one other thing: What could prevent the prover from giving you two different colors at random for each query ? -> This issue doesn't exist if the envelopes are real, meaning that the prover laid them before your query and you make your choice after that so that the prover can't generate the answer on the fly. It means that the prover has to have a working 3-colored map to not be caught cheating eventually.
''Fermat's Last Theorem follows as a corollary" is the perfect answer to "[...]a truly marvelous proof of this, which this margin is too narrow to contain." Fermat would be proud
18:20 "Any formal mathematical statement can be converted into a map. And, I should stress, this conversion is efficient. There is a SIMPLE ALGORITHM KNOWN TO ALL..." 18:55 "Very simple, efficient, known to everybody" Just had to laugh at these.
@@AtanasNenov No? You'd still need to find a coloring of the map after converting the riemann hypothesis to a 3-coloring problem. But 3-coloring is hard, so you can't do it effectively.
@@AtanasNenov No. What we could do is generate the map only for the Riemann's hypothesis, which would be VERY HUGE. With that uncolored map, we learned nothing. Then, to prove the hypothesis is true, we'd have to color it with three colours. And doing *that*, specifically, is computationally unfeasible. Even though we have a simple algorithm that would eventually do it, if possible, the process would take more time than the age of the universe.
So I could use zero-knowledge verification to prove that the three-color mapping of the four-color map theorem is a valid, but my trust in the zero-knowledge verification process is contingent upon my trust that the four-color map theorem is valid. Therefore the zero-knowledge verification is either redundant, because I already trust in the theorem it verifies, or ineffective, because I do not trust in one of the theorems it is based upon.
@@Faladrin I don't know what you mean. Yes, this was sort of tongue in cheek, but I don't see what it is about zero knowledge proofs that you think I've missed.
This was a hard video to concretize but Avi just won the Abel prize partially for such work so I guess it makes sense that it's hard to bring down from the abstract :)
I have a computer science degree. I don't understand how you would "catch" the liar... In his example the verifier would need to know the coloring right?
Long story short: it's not a proof. It's evidence that a person *probably* knows a proof. NP-complete problems have a forward direction which is easy, and a reverse direction which is very difficult. The zero-knowledge "proof" is showing that you can do the reverse operation as many times as you like. Statistically you could be guessing the answer by chance but you repeatedly do this to increase confidence that you know how to do the reverse procedure, and therefore have a proof.
You can reduce the margin of uncertainty as much as you like. If you did an infinite number of checks, the probability of pure chance not being detected drops infinitely low, thus zero.
@@wizard7314 I'm not sure. Isn't it a bit like Nyquist-Shannon, in which a finite number of discrete samples can amount to a continuous truth "within a frequency range" - ie. there has to be a number (and/or sequence) of tests that can in fact guarantee a proof, based on how many "countries" there are to color (the desired maximum frequency) ? EDIT: I'm talking about a concrete threshold between "exceedingly unlikely to be wrong" and "proven" basically?
Yes this is statistical in nature. You can never be 100% sure he isn't cheating. even if he threw random colors on the map there is a 2/3 chance every time that the 2 countries you pick are different colors. So after K iterations the chance he was cheating using a totally random coloring each time your "risk" would be of the order (2/3)^K which is always greater than 0.
Really interesting but so many questions. An example would be awesome. From what I understood: 1. Start with a hypothesis. 2. Prove the it. 3. Convert the proof into a 3 colored map. 4. The coloring can now be verified without revealing the solution. Questions: 1. Is the "shape" of the uncolored map determined by the original hypothesis or by the proof? If the proof determines the shape of the map, then: A. Doesn't knowing the shape of the map give some information? (Therefore not Zero Knowledge Proof) B. Would an alternate coloring (assuming one exists) be an alternate proof? C. If I can color the map can would it mean that I also have a proof? D. Assuming that I have verified the coloring in your supposed proof, how do I know that it links back to the original hypothesis as opposed to a random 3 colored map? If the shape is determined by the hypothesis then i guess it answers most of the questions above. 2. Every finite map either can either be 3-colored or not. If yes then you have proved the hypothesis, if not then the hypothesis is false. A. What about an unprovable hypothesis "Gödel's incompleteness"? Will it also have a map? If so will it be 3-colorable or not?
Something he rather glosses over is just how quickly these maps grow with the complexity of the problem. Even an apparently “simple” proof, say that there are infinitely many primes, balloons to a very large number of strictly formal statements, and hence a very large map.
Yes. You have to start with the absolute basics. You even have to construct natural numbers from scratch (see Peano arithmetic). I think he kind of misrepresented the complexity by saying converting statements to maps is a "simple" translation
/me hums... "I'm so dizzy, my head is spinning Like a whirlpool, it never ends And it's you, Avi, making it spin You're making me dizzy" ty for posting! :)
If you take the statement discussed in this video regarding the ability to convince a verifier (with as close to 100% certainty as you desire) that a map is 3-colorable, by only revealing random pairs of neighboring colors chosen from a random permutation of such a coloring, then that statement can be converted into a map. And that map would be, according to the video, 3-colorable. And you could convincingly demonstrate that the map is 3-colorable without revealing any information, using the same method. I believe this is what you're looking for.
It's moments like these when you feel the beauty of mathematics and formal logic. When it truly shines. You can have a cake and eat it. Er... I mean, you can have a proof and not tell it in details. And it still works. *convincingly shows why* "But I want to know the proof." "You don't need to know the proof. Here's the proof you don't." "I don't need to know the proof." It has the beauty and style of a Jedi trick, only with a solid mathematical ground under it.
Does anybody know what happens to undecidable statements when you construct their equivalent 3-color map? Whether a map is 3-colorable or not seems to me to be always either true or false, but Godels incompleteness theorem (also referenced) would seem to imply some maps are neither. This NP stuff on proving is super interesting but indeed the video left me with many more questions!
I THINK it works like this: The colorings encode proofs of statements. For a statement X and a map MX, the existence of a 3-coloring for MX is equivalent to a proof of X. The negation ~X has a map M~X and a 3-coloring for M~X corresponds to a proof X is false. If X is undecidable from your axioms that means there is no proof of X nor a proof of ~X. Equivalently there is no 3-coloring of MX nor a 3-coloring of M~X
This is so interesting, I feel like I get the main point but now I'm really interested in the algorithm that transforms proofs into maps and vice versa and *how/why* it works. these connections are so interesting and beautiful, it makes me want to become a mathematician
You should ! The topic is super interesting, I'm not sure how much they would teach it in math tho, as it is more central to more computer science things
mark van dijken You and everyone else too! I hope they eventually reference some course or lesson on the topic. I don't need a concise 30-min video. I'd gladly speed weeks getting into it.
You as a verifier could generate the map yourself from the statement that is supposedly proven, then tell the prover to color it in. Or convert the map back to the statement and check they are identical. The map and the statement are the same thing in different forms and can be translated perfectly back and forth. Then you can verify that the coloring is actually valid (only three colors used and no neighbors the same color), either by just looking at it and checking it, or alternatively if the prover is paranoid and don't want to let you steal the proof, by the zero knowledge (envelope) method. Then you know that the statement is true.
I don't comprehend - in the example with the map I can fake a proof that I can color any map with just 2 colors. Because when the verifier ask me about any two neighboring countries, I'll always show two different "random" colors.
Regarding an example, I did zero knowledge proofs at University, and we did one example, which was graph isomorphism, which was really hard to wrap my head around. The lecturer then said every other example is vastly too complicated to be covered in the course. And because the only example within the scope of the course is graph isomorphism, it won't be on the exam haha.
What about Gödel’s Incompleteness Theorem? If that says that there are statements that cannot be proven to be either true or false, and NP completeness says that every statement can be converted into a map, there must then be maps where it is impossible to find a colouring, but also impossible to prove that there isn’t one. Would these maps be infinite, or how does this work?
The way I believe it works is as follows. Let's say you have a statement X. There is a map called MX. If there exists a proof of X then MX can be colored with 3 colors. A specific proof is a specific coloring. If X is false then that means ~X ("not X") is true. There is a map M~X. If there is a proof that X is false, i.e., a proof of ~X then there is a coloring of M~X. If X is undecidable then there will not be a proof of X nor a proof of ~X and so neither MX nor M~X will have a 3-coloring. These maps cannot actually tell you anything about the inherent "truth" of various mathematical statements. They can only encode the existence of proofs following from a specific set of axioms. Gödels theorem then basically says that for any system (e.g. Peano arithmetic, or ZFC) there will be some statement X that can be encoded in that system, and thus for which we can construct a map MX, but for which both MX and M~X won't have a 3-coloring.
Sorry to clarify, there will be an X we BELIEVE to be TRUE that can be encoded in the system but for which there doesn't exist a proof (coloring) of X nor of ~X.
But what about unverifiable statements? Can these be translated in a 3-coloring map problem? Why does it not contradict Gödel's incompleteness theorem?
Only formal systems of sufficient expressivity are incomplete. Less powerful ones are complete. Since satisfiability of boolean formulas is an NP-complete problem, I'm guessing that the formal system involved is boolean formulas which are (syntactically) complete and thus wouldn't allow you to express unverifiable statements. No boolean statement -> no map.
@@AubreyBarnard what you say must be true, but he was giving examples from numbers or higher logic, not just propositional logic. So either his exposition is misleading, or there is something I don't get. The way he puts it, it looks like Godel's incompleteness is violated.
AFAIK the colored map represents both the statement and the proof. Unverifiable statements does not have a proof, thus there exists no colored map for them.
RIght? I'm so interested in the specifics. Like whats the simplest statement you can convert, and can you please draw it and explain how it captures the statement?
Given that some people would spend that time...arguing with people on the internet who won't change their minds, watching so called reality TV, doing drugs, getting drunk, or reading 50 shade of grey, I think you can easily justify the 33 minutes vs those actions :)
You: I have a zero knowledge proof of this problem. Hacker: Tricks you into opening NOT neighboring envelops in order to discover the whole map through finding envelops with the same color.
Except...the color scheme can be shifted (1 of 6 variations I think was mentioned) randomly. You could repeatedly query until every 'country' on the map was revealed...and still not know what the final answer/3-coloring of the entire map is. Hence the term 'zero knowledge'.
@@ckshreve We're not interested in the colors themselves, any more than we care about whether we call a variable x or y. A given color is just an abstract label. What we are interested in is the structure of the coloration, which directly corresponds with the structure of the proof we want to find out.
@@ckshreve if we verify three countries A, B and C are different colors we can color the rest of the map using A B and C. Youd just need to cycle through them till theyre the same color
Can this be inverted? Meaning, go from a map to a set of statements? Because it would be fascinating to create arbitrary maps, find a 3-coloring, and then know to what problem I just found a solution!
Also, since there are statements that are true but cannot be proved to be true, are there maps that are 3-colorable that can't be colorable? I am facinated, but seems like a lot that's needed to understand here.
If I understood the video correctly, it is not. If you have an improvable statement and translate it to a map, the map wont have a three coloring. But if you have a non-3-colorable map and translate it to a statment, it will only tell you, that there is no prove to the statment, not that it is false.
@@AbelShields I would say yes. But persumably thats hard ... mind that to show that it is unprovable you additionaly would have to show that you also cant disprove your statement.
@@tth-2507 Proving there is no three colouring is in principle easy (but slow); you just have to search all colourings. You can similarly show that the negation of the statement has no three colouring, and hence no proof.
How is the secret envelope mechanism implemented in practice? I know you can use a cryptographic commitment scheme. To a casual viewer though, that's kind of an important detail. A lot of schemes are possible if you're allowed to assume magic.
If "we tried to prove you wrong a buncha times, and couldn't" worked as a proof-of-proof, we can "prove" that someone has a proof to the Collatz Conjecture.
Imagine someone hands me a proof of the Collatz conjecture. There's 2 ways I could try to prove them wrong: A) Shred the proof they handed me. I don't need that. Then guess a random number and run it through the Collatz function a bunch of times until I reach 1. Repeat many times. B) Flip the proof open to a random page and check if the author made an error in reasoning on that page. Repeat many times. I'll never be too certain that the Collatz conjecture is true by doing A. But if I do B, pretty quickly I'll have checked every page in the proof, and will be fairly certain that the proof is correct. (Or will have found an error if it is false.) Zero knowledge proofs look like B, not like A. (Just with weird-looking "encryption" of the proof.)
I think the idea is The map would always be 3colorable no matter what, but if you had a proof, and put it into algorithm, then the result would be a completed valid 3 coloring of that map. And not that, say, it could be reversed. Or that you could know right away if a statement was provable, by looking at the map and finding it could not be 3colored. Crypto is all about that, how can you in encrypt/decrypt, while everyone is listening, without giving out either keys. Or to make sure a chain of information is validated, without knowing the original source.(crypto currency).
So basically, if the proof is correct then the map that represents it is 3-colourable, and if the proof is wrong then there will be at least one space that is touching all three colours. And you can ask questions about regions on the map, like "Is X touching Y?" or "Are X and Y the same colour?" But there are 6 possible colour schemes for the map that are otherwise identical but for the order of the colours, and the person with the map can palette-switch between them at will. For instance, you find out 1 and 3 are not touching each other and are told they are both blue (but they could also both be red, or both green); 2 and 4 are not touching and they are both blue; but when you ask about 1 and 2, they might be touching and one is red, the other green, then 3 and 4 are not touching and are both blue ..... The person with the map can avoid giving away enough information to allow you to reproduce the map yourself, because you only know "same or different"; but there are still two equally-likely kinds of "different", and the map holder can switch between possible colour schemes from one question to another and so prevent you from fully recreating the map; for instance by claiming every non-touching pair to be "both blue" and every non-touching pair to be "one red, one green". This way, you can be presented with an impossible composite of the six equivalent maps. If the proof is wrong, their map will have two regions of the same colour that are touching; and the map is finite, so if you keep asking questions long enough, you are bound to turn this fault up eventually -- "touching, blue and blue" probably! But the more questions you ask without finding a colouring violation, the greater the confidence you can have that the map _is_ three-colourable, even although you can never properly recreate the entire map at once because the holder seems to insist every region in it is blue .....
I have to echo what everyone is requesting: It would be AWESOME to do a follow-up video of an example translating a theorem into a Map (ideally a super simple theorem, even "trivial" like 0+1=1 or two parallel lines don't cross ) The power of such a mathematical tool is immense! (I wonder if there are ways to translate theorems into different Math problems, say changing the "theorem" 2+2=4 into a polynomial function and if there is exactly one x-intercept then it is true. Maybe Colour-map translation is only one way to do this, and there is an infinite number of ways to do this, some more efficient than others. Thinking further, maybe there is a tradeoff between ease-of-translation and ease-of-resolution, defined by an equation relating the two.)
This is true regardless of the mapping theorem. If you have enough time you can type every possible document using every possible symbol, and that would include the proofs to every provable mathematical claim (and would also include my grandmother's telephone number or the number of ways a monkey can scratch its bottom)
It almost seems as if there should be some way to generate random 3-colored maps and then reverse engineer them to declare random proofs. I assume there are infinite many possible 3-colored maps, and therefore infinitely many mathematical proofs? Or are there just infinitely many variations of the same proof? ie infinitely many ways to demonstrate that AxB = BxA
I didn't understand how he is caught cheating if he doesn't have a proof for a three-colour map problem? If he has proof, the two colours will be randomly chosen from the 6 permutations. This leads me to believe that we won't have random combinations if he cheated and so he can be caught with near 100% probability by quizzing him a million times. But I don't see how the combinations are not random when he cheats. Can someone please help me make this connection?
Being caught cheating would mean opening an envelope and finding a fourth color or opening two adjacent ones and finding the same color in each. Both of those scenarios would prove 100% that the prover doesn’t actually have a proof. The randomness of the colors isn’t what verifies the proof. The point of the randomness is just to make sure no information is conveyed.
The piece I’m missing is core to the “zero knowledge” principle - how answering a single “any two envelope” question proves anything - if the answer could have been provided by the asker, how does it prove anything? i.e. if I can answer with any two random (different) colors, how does that convince the asker anything at all?
Afaik (after watching this video), the reason for this is, that the prover fixates all colors (the whole map coloring), before knowing which neighbours are chosen. Maybe it's easier to understand if you split the process into 4 steps,: (1) for each country (map tile) the prover gives the verifier a sealed envelope with the color of this country. In total it's a 3-coloring of the map, but sealed so the verifier can't see them. (2) The verifier asks for two neighbouring countries. (3) The prover provides the keys to unseal the envelopes of these two countries. (4) The verifier unseals those two envelopes and checks if the colors are distinct. So in essence, the prover encrypts a 3-coloring and then the verifier is allowed to decrypt two tiles of their choice. Because it is fixated, the prover can't just provide 2 random distinct colors (only a random coloring of the complete map which likely includes neighbouring tiles with the same color)
@@aapianomusic Yes, after rewatching the video, you are absolutely correct. I neglected to consider that the two countries in question aren't known ahead of time to the prover, so they have to provide valid pairs of colors for ALL pairings of neighboring countries, not just a single pairing. Thanks for your comment.
@@TheJonHeese You still are onto something that was not clear in the video though. The colouring is claimed to be fixed at the start, but Avi makes it clear that if he actually showed you the real colours each time you open the envelopes, then he's revealing the proof more and more with each pair you open. The way it becomes zero-knowledge is that Avi is actually allowed to permute his colourings each time you ask (and he's also allowed to refuse to answer some questions, which is another issue that could lead to the proof being unsatisfactory). If he's changing the colourings each time, then it's not fixed. So if you choose three countries that all border eachother 1,2,3, and want to know if they are all different, then you might test 1&2 then 2&3 and then 1&3, the results should all be distinct. However, since Avi is allowed to change these before hand, then how can you know that he's just permuting them (which would be a valid proof, since permutation doesn't affect the proof) and not simply changing his answers each time so that he never contradicts you. You can't compare colours you learned from two different tests, so you can't catch him out by using information from 1&2 (say red&green) and 2&3 (say red&blue) to conclude that there was an error... I suppose there is a mathematical way to prove when the answers you've been given can't possibly be a valid permutation, but naively it seems like Avi could just respond 'red & green' to every question and "prove" that all bordering countries are distinct.... you need some way to fix the colouring AND fix the permutation process so that you know Avi is actually consistently describing this map...
@@sfreer6044 the idea is that, if he has a valid 3-colouring, no 2 neighbouring envelopes that you pick will EVER have the same colour (regardless of if he permutes between guesses, and regardless of how many envelopes you check), whereas if he doesn't have a valid 3-colouring, you are likely to eventually (after an arbitrarily large number of picks) stumble onto a pair of neighbouring envelopes that do contain the same colour, which would imply that he didn't have a 3-colouring.
@@cheeseburger118 yes, but if he doesn't have a 3-colouring why can't he still just consistently make up pairs of different colours to always pass? I assumed it would be because the answers need to form a self-consistent pattern, but this would eventually add up to give the colouring. Without any need for consistency between responses to the 2 envelopes, why not just say "red and blue" everytime and never fail, but never prove anything? I'm missing what stops this exploit from working.
17:26 does the agent asking the questions always have to inquire about two neighbouring countries? If he doesn't, he could in O(M!) time uncover the exact colouring of the prover, where M is the maximum numbers of colours used. M is very low compared to the number of countries, so it would even be efficient to reconstruct the colouring
He said in passing if the countries were not neighboring then prover didn't have to answer at around 31:45 . But even if the prover did, I think it still would be zero knowledge. The question here being "could you simulate the interactive proof by yourself". And I think the answer is yes as new, independently chosen permutation of colors are put in the envelops in each round.
I was thinking about whether I should give up half an hour to watch a mathematical video (I'm not a mathematician) and I should say that I do not regret my decision. The result is quite amazing.
@@Danicker by provable i mean possible to prove an answer to, yes or no. also you could just negate it and prove the negative (instead of proving A is false, prove not A is true)
@@MrRyanroberson1 But what would happen if try to use this technique to prove a mathematical statements, because I cannot know a priori if the statement is decidable. Since any mathematical statement can be encoded with 3-Sat(Not sure if its 3-sat, or sth different), It should also be possible to encode undecidable statements and then use a prover to get a proof for it. Ofc such provers don't exists atm as far as I know
@@thegreatdream8427 Just because the mathematics community 'doesn't allow" people to do it doesn't affect whether or not you can construct a graph of it, but there is might be some more rigorous reason why that is the case.
@@MK-13337 The statement itself may be in English, but I was referring to the mathematical translation of that statement. I don't believe it is a linguisticall paradox, it is just the method I used to communicate the vague notion that "I am wrong". I don't see a reason why you couldn't write it mathematically.
so mind readers (who guess the card. number, etc) can prove that they have a magical power to read minds using zero-knowledge proofs In fact, they do it every day. It is their job.
Well, if you a suffiently efficient way to create a non-perfect 3 colored map with some small error, you could fake your way out with the same error. Does this mean that to have a certitude of 99.9999%, and if you know faking it has a error of around 0.00001%, you would need to probe around 10^13 times? And if you don't know how efficient a faking algorithm is it's basically pointless?
The only thing that really bothers me is that the zero knowledge proofs rely on inductive reasoning rather than on deduction (they are not “proofs” in the usual sense but rather provide “proof” in the sense of evidence). I guess the goal is just to attain “conviction” in the verifier but was anyone else bugged by this? Thanks I’d love to learn more
What part didn‘t you understand? In short: every statement can be converted into a map. Every proof (true statement) is a 3-coloring of that map. If I show you a three coloring of the map I have given you a proof (indirectly), as everything can be converted back to mathematical statements. But wait because I showed you a specific coloring I also transmitted information. In order to make it zero knowledge you get to ask me 2 neighbouring countirss of the map, which I colored in before you asked. If they are opposite you‘re a little bit convinced. Now I color it again in a different way and let you ask me again. If they‘re opposite again you‘re be a little more convinced. Ok we repeat this until you‘re 99.999...% sure I really do always color the map with a 3 colors.
@@screwhalunderhill885 thank you for the "too smart/wordy didn't understand" Feels like that's not even a proof because... You're getting information in the form of a limiting process... Like when do you declare it's true - 75%? 99.99999%? Feels arbitrary _i guess you gave me a no knowledge proof_
Fermat's Last Theorem: th-cam.com/video/qiNcEguuFSA/w-d-xo.html
Four Colour Map Theorem: th-cam.com/video/NgbK43jB4rQ/w-d-xo.html
Gödel's Incompleteness Theorem: th-cam.com/video/O4ndIDcDSGc/w-d-xo.html
P v NP: th-cam.com/video/dJUEkjxylBw/w-d-xo.html
At 16:50 I'm pretty sure you were supposed to close all the envelopes belonging to the same column, not all reds
His claim that every mathematical statement can be converted to a graph that is 3-colorable iff the statement is true is wrong. For example, given some formula in first-order logic (i.e. something like "for all x there exists y such that x does not equal y"), the statement "the formula is always true" cannot possibly always be converted to a graph. This is because the question of whether an arbitrary formula is always true is known to be undecideable - there is no algorithm which can determine the answer. If his claim were correct, we would have an algorithm: simply convert it to a graph and then check whether the graph is 3-colorable.
Ah, I see what you are doing. Just throw enough amazing content at us and we'll get distracted and go away. Well we aren't fooled so easily! We want to see the conversion of a mathematical statement (or two) into a 3-color map! :D
@@rosekunkel4317 So you're claiming that checking whether an arbitrary graph is 3-colorable _is_ decidable? Why is this so? I don't think the resulting graphs need to be finite.
Why do I get the feeling that he disproved his own statement with the example of the three countries in a triangle rounded by a 4th one? That is not possible to be three-coloring, but still a valid configuration. Or what am I not getting?
/*edit*/ I made some drawings for myself and I can indeed color anything with in most cases 3 colors, but there are exceptions where I have to use 4. So if that is what is meant I find the name 'three-coloring' very confusing to use since it can be more. Maybe I'm just to logical as a computer-engineer.
Finished watching and I still have zero knowledge
Success
I was pretty sure the very first part of the conversation was him displaying the very example of the whole video lol
But you have to prove that
I scrolled down just to look for this comment, was not disappointed.
But can you prove it? :)
would be nice to see an example of translating of statement and proof to a map with coloring
I think the keywords to look for are SAT to 3-colorability. The steps in-between are turning a graph into a map, and turning a proof into a logic expression in the appropriate form.
Thanks kibrika
I typed “SAT A to colouring” into google images and was presented with humpty dumpty outlines 😂
@@kibrika thanks
That sounds like a video for numberphile2... Oh wait
Somehow this 30 minute video gave me better understanding about zero-knowledge proofs than 2 hour-long lectures on the subject I had a few years ago.
This video feels like a zero-knowledge proof of zero-knowledge proofs.
I agree with others, we need a followup video with a practical example. This is interesting, but too abstract.
Bump.
You have two pens of different colours. You want to prove to your friend who is colour blind the pens are different colours without revealing the colours or anything else about the pens.
You say hold one in each hand, put them behind your back, either switch or don’t.
If I guess if you switched or not right once, either I guessed right, or the pens are different in some discernible way to me, the prover. Ie The chance I was telling the truth about there being a difference in the pens is 50%. If we do this game twice, 75%, 3, 87.5%, and so on until you’re sure enough the pens are different.
The key here is I’ve proven the pens are different to you without revealing anything about them. This is very valuable in cryptography
@@test-sc2iy thats a really helpful explanation! Thanks
What you need is two semesters of Computational Complexity.
ты че не понял? хаха
Even for Numberphile, this video is just absolutely insane.
It's Numberphile2: double the difficulty.
@@rogerr4220 this video belongs on Numberphile²
@@rogerr4220 The basic concept isn't difficult to get. In less precise language, you're basically proving to someone that the proof (of some problem or the other) you claim to have is legit, without actually revealing the proof itself. To use a poker analogy (this is really imprecise mind), it'd sorta be like convincing everyone at the table that your hand is the winner, without actually showing your cards. How you'd do that in poker is beyond me, but the effect is the same - they believe you, despite not actually knowing what you've got.
This has to be the worst most unfulfilling Numberphile video I've ever seen. It's 33 minutes of my life I'll never get back again.
@@ArawnOfAnnwn That isn't a valid analogy because poker is a game where the objective is to persuade, not prove.
Professor Wigderson is one of the nicest, kindest people - he once took an email from me - a novice - and was gracious and generous with his time.
please do a follow up on how to convert logical statements into a 3 colourable map
Please
+
You'd first need several college-level courses on set theory and formal logic to understand it first.
@@ObjectsInMotion Ah, too advanced then for Numberphile's TH-cam audience? I tend to think not. Just list the educational dependencies up front. No need to cover them in their entirety in the video.
From messing around on paper and reading a bit:
You start with a palette of F, T, and B.
This palette is just a triangle of nodes.
Whatever F is colored as means false.
Whatever T is colored as means true.
B is an auxiliary node.
You enforce the law of noncontradiction by connecting to B.
You encode a premise by connecting it to both B and F. This forces it to be true.
You encode a negation ~X by connecting it to both B and X.
You encode "X or Y" with another triangle.
One of the nodes of the triangle is T. Another node is connected to X. Another node is connected to Y.
The nodes that aren't T must be either BF or FB.
X - B - F - Y or X - F - B - Y
If X is F it forces the connected node to be B.
F - B - F - Y
And this forces Y to be T.
F - B - F - T
This works symmetrically.
You can construct any statement in propositional calculus from or and negation.
This means you can encode any Boolean satisfiability problem.
I'm not sure where to go from there.
this is probably the best vid on zkps out there
I don't think I've ever understood any concept less in my life, but I still really enjoyed listening to Avi, and it's always interesting to see these complex mathematical ideas, even if they make my head hurt.
"I can prove X" -> "I know what keys open that door"
Whether X is true or false-> Whether the door opens or not
The mapping of the proof -> The key
Any statement can be a key, Only true statements/proofs open the door, however Party B does not know the internal mechanisms nor the keyshape. Party A has knowledge of the proof, can prove they have this knowledge by correctly identifying keys that open the door. They know whether the proof/statement they made is true and can be said to know the internal mechanisms.
Three parts make it zero knowledge. Completeness (Party B will be convinced that Party A has proof, the probability of Party A picking correctly approaches 100% ), Soundness (Party A cannot cheat if they do not have the proof/The probably of Party A picking correctly gets closer to 0% if the statement is false), and Zero-knowledge.
What makes it zero-knowledge is that Party B cannot look at the key. Party A looks at the key, Party B checks whether Party A picked correctly.
This process is repeated, since it is 50/50 for the first time and it gets progressively more unlikely that Party A is guessing as Party A correctly identifies valid keys.
The mapping is more like: The lock is the proof, the keys are the various different mappings, only true proofs have keys that open it. Both Party A and Party B can know how keys are made, but not necessarily how the lock functions. Since the method of key-making is known, you can't make false keys and there is no guessing.
In less precise language, you're basically proving to someone that the proof (of some problem or the other) you claim to have is legit, without actually revealing the proof itself. To use a poker analogy (this is really imprecise mind), it'd sorta be like convincing everyone at the table that your hand is the winner, without actually showing your cards. How you'd go about doing that in poker is beyond me, but the effect is the same - they have to believe you, despite not actually knowing what you've got.
@@ArawnOfAnnwn "How you'd go about doing that in poker is beyond me," why would you pick an example of which you don't know how to prove it? the whole point is knowing a way if how to do that...
@@sofia.eris.bauhaus "I don't think I've ever understood any concept less" - I explained the concept. You can feel free to explain the mechanism if you feel up to it.
It's like proving that you know the password to a computer by hiding the keyboard from view and typing in the password. Anyone can see that you unlocked the computer, so you must know the password, but that doesn't help anyone else figure out what the password is. The only new information they have is that they know you've proven you know the password.
It would be extremely helpful to see how to convert even a trivial statement into a map, as well as how to convert a 3-coloring of that map into a proof of that statement. Or at least a link to some paper where that process is explained, searching online returns no clear explanation.
Like he said, it’s using only formal proofs with symbols only, and a map would be huge for even a simple statement, so you would not really be able to translate it by hand or be able to comprehended if made by a computer. However, computers can communicate with each other in this language.
If I'm not mistaken, it takes a lot of definitions and tools, for example it probably goes through SAT and then through 3SAT to go to graph (map) colouring
@@TheKikou18 yes. Basically, no matter what branch of mathematics your statement is in, if first needs to be converted to pure logic. Even concepts as elementary as counting numbers and arithmetic are notoriously laborious to translate in this way (as evidenced e.g. by the lengths Whitehead and Russell had to go to just to show 1+1=2). I can scarcely imagine how hard it would be to encode concepts like arbitrary triangles in Euclidean geometry in this language.
@@varunachar87 I mean he said in the video that it can be explained even to a high school class, so I think that it would be an appropriate topic for Numberphile - there must be some explanation in between "its true" and "here's how to do it all out by hand."
@@elireville7206 I think this _is_ the high school-level explanation.
18:20 I'd love to see an example of the smallest map that proves or disproves something, and a description of the theorem it proves. Great video.
Yes, this. A trivial or basic example would be great.
I'd love to know what "1 + 1 = 2" and "1 + 1 = 3" looks like.
@@Galakyllz Even those would probably be pretty big projects, just in formal logic alone, not to mention translating it into a map? idk
Unfortunately in general, these maps will be absolutely huge, even for the most simple proofs because the conversion consists of several steps (proof → formal proof → proof-checking turing machine → boolean expression in CNF → graph → planar graph). Every one of them will most likely turn its input into an even bigger output.
@@waldtrautwald8499 Are there pure logic statements that would produce graphs/maps that are small enough to understand?
Something like 1≠0? Or 0∈ {0,1,2}?
@@iveharzing You want a (somewhat short) boolean formula that is satisfiable iff your statement is true. This seems doable for your examples, depending on how you actually encode them.
The size of the corresponding graph is then linear in the length of the boolean formula (in CNF). So the graphs shouldn't be too large. The key step is the reduction from SAT to 3-COLOR. There are some great visualizations online.
Knowing a property about a collection without knowing anything about the individual elements reminds me of quantum entanglement. I imagine there are interesting overlaps between NP completeness and quantum information theory.
Congratulations to Avi for winning the Abel Prize!
I came to this video after I watch 2021 Abel Prize ceremony.
To summarize:
1) you can show a map can be 3 colouring without revealing information about the colouring
2) you can transform any statement into a map
3) if that statement is true, you can do a 3-colouring on that resulting map
C) you can do zero knowledge proofs for any statement
I am hoping that (3) is "If the statement is provable then you can do a 3-colouring on that resulting map", since otherwise this seems to conflict with Gõdel incompleteness.
@@anthonyberent4611 I'm not sure how Godel's factors into this at all? Eric's comment is perfectly correct.
To be even clearer: 2) you can transform any statement into a map and any proof of the statement into a coloring of the same map.
@@anthonyberent4611 Only NP statement's can be turned into maps, the unprovable statements guaranteed by the incompleteness theorem all lie outside that set.
There are short statements whose shortest proofs are arbitrarily long (in any axiomatic system able to interpret basic arithmetic). To get a map of fixed finite size, you need a fixed finite bound on the length of proof that you'll accept.
As for NP: "Statement X has a proof of length
@@RobinDSaunders So, are you saying that to create the map for a statement you need not just the statement, but also how large a proof you will accept for the statement? In that case, presumably, if the map you create is not three colourable, it doesn't tell you that there is no proof, simply that there is no proof shorter than your chosen N.
I love this, but I understand why its not on the main channel. Its not a bite-sized digestible chunk, but I think this sort of thing is fascinating and maybe its worth learning about seriously if I think so.
Honestly I wish this video h ad been on the main channel. This is one of the most profound numberphile videos I've seen; so much so that I've just spent half an hour trying to remember where I saw it to rewatch it.
This is way too awsome to be put on the second channel. Now I want to know, how a statement (even a very simple one) can be translated into a 3-coloring-map problem. Or is that also a zero knowledge thing?
Yeah I really wish he gave an example, no matter how simple.
A simplest mathematical statement will still correspond to a map of size 1,000 or more 🤣
I'm waiting for the followup. Even a simple description, name, or a link would suffice.
the guy proving the existence of zero knowledge proofs was like: lemme prove that i have a proof that you can prove that you have a proof you don't want to tell
Great, so what's the proof?
-Won't tell you, but please take a look at this map of the statement...
I am at the stage of dealing with proofs in my maths study. Some are like trying to wrap your head around a pole while singing opera and messing with a rubiks cube.
Tonio Kettner I don't believe you. Prove it. But then you wouldn't believe that I don't believe you, wouldn't you?
@@ZandarKoad thanks for explainig me my own joke
@@toniokettner4821 Hey, a joke is always funnier the 2nd time you hear it!
There are things I didn't understand at first but I think figured out :
Say you have a map a and verifier that always pics the same country and ask to compare it to all the other ones, once the verifier has compared all the countries to the initial one, he will know for sure one of the colors. The verifier can then repeat the process with an other country with a different color from the first country, and he will the know for sure the exact three-coloring of the entire map.
-> I guess this issue doesn't exist if you're only allowed to probe neighbouring countries.
And one other thing:
What could prevent the prover from giving you two different colors at random for each query ?
-> This issue doesn't exist if the envelopes are real, meaning that the prover laid them before your query and you make your choice after that so that the prover can't generate the answer on the fly.
It means that the prover has to have a working 3-colored map to not be caught cheating eventually.
Yeah I think what would clear things up for me is an example of how verifier can catch a fake proof
This might be the greatest sleight of hand in mathematics. Brilliant.
''Fermat's Last Theorem follows as a corollary" is the perfect answer to "[...]a truly marvelous proof of this, which this margin is too narrow to contain." Fermat would be proud
I conjecture the heart notation on the white board was key to his insight.
18:20 "Any formal mathematical statement can be converted into a map. And, I should stress, this conversion is efficient. There is a SIMPLE ALGORITHM KNOWN TO ALL..."
18:55 "Very simple, efficient, known to everybody"
Just had to laugh at these.
Known to all genius-level math wizkid
Known to everyone, minus everyone in the comments.
Yup, doesn't seem to be so easy as it sounds. If it were, we could check if Riemann's hypothesis is true (even if we can't build the formal proof).
@@AtanasNenov No? You'd still need to find a coloring of the map after converting the riemann hypothesis to a 3-coloring problem. But 3-coloring is hard, so you can't do it effectively.
@@AtanasNenov No. What we could do is generate the map only for the Riemann's hypothesis, which would be VERY HUGE. With that uncolored map, we learned nothing. Then, to prove the hypothesis is true, we'd have to color it with three colours. And doing *that*, specifically, is computationally unfeasible. Even though we have a simple algorithm that would eventually do it, if possible, the process would take more time than the age of the universe.
I Once accidentally Proved The Collatz Conjecture in my dream. Now I know why I don't know anything about it.
One of the best numerphile videos I've ever seen.
Proof of the four-color map theorem can be zero-knowledge verified using a three-color map.
I need a proof of that!
Interesting! Do you have a source for the proof?
So I could use zero-knowledge verification to prove that the three-color mapping of the four-color map theorem is a valid, but my trust in the zero-knowledge verification process is contingent upon my trust that the four-color map theorem is valid. Therefore the zero-knowledge verification is either redundant, because I already trust in the theorem it verifies, or ineffective, because I do not trust in one of the theorems it is based upon.
@@sk8rdman You are either joking or have missed the entire point of zero knowledge proofs.
@@Faladrin I don't know what you mean. Yes, this was sort of tongue in cheek, but I don't see what it is about zero knowledge proofs that you think I've missed.
I'm halfway through the video and already completely amazed! This is amazing!
This was a hard video to concretize but Avi just won the Abel prize partially for such work so I guess it makes sense that it's hard to bring down from the abstract :)
Someone who truly understands the material can break it down and reverse the process by which they came to understand it
Great video. Should this have been on the main channel?
I didn't even realize this wasn't on the main channel
I have been staring at this video for 30 minutes, and I have an urge to not erase anything for some reason.
This was absolutely fascinating, thank you so much
I have a computer science degree. I don't understand how you would "catch" the liar...
In his example the verifier would need to know the coloring right?
Long story short: it's not a proof. It's evidence that a person *probably* knows a proof. NP-complete problems have a forward direction which is easy, and a reverse direction which is very difficult. The zero-knowledge "proof" is showing that you can do the reverse operation as many times as you like. Statistically you could be guessing the answer by chance but you repeatedly do this to increase confidence that you know how to do the reverse procedure, and therefore have a proof.
You can reduce the margin of uncertainty as much as you like. If you did an infinite number of checks, the probability of pure chance not being detected drops infinitely low, thus zero.
@@psicommander Not a finite proof, if you want to get technical.
@@wizard7314 I'm not sure. Isn't it a bit like Nyquist-Shannon, in which a finite number of discrete samples can amount to a continuous truth "within a frequency range" - ie. there has to be a number (and/or sequence) of tests that can in fact guarantee a proof, based on how many "countries" there are to color (the desired maximum frequency) ?
EDIT: I'm talking about a concrete threshold between "exceedingly unlikely to be wrong" and "proven" basically?
I still don't get how it was proven that all NP-complete problems have zero knowledge proofs.
Yes this is statistical in nature. You can never be 100% sure he isn't cheating. even if he threw random colors on the map there is a 2/3 chance every time that the 2 countries you pick are different colors. So after K iterations the chance he was cheating using a totally random coloring each time your "risk" would be of the order (2/3)^K which is always greater than 0.
This is probably the best explanation I have heard for zero knowledge proofs
OMG! Avi! My favourite entropy extractor algorithm inventor.
Really interesting but so many questions.
An example would be awesome.
From what I understood:
1. Start with a hypothesis.
2. Prove the it.
3. Convert the proof into a 3 colored map.
4. The coloring can now be verified without revealing the solution.
Questions:
1. Is the "shape" of the uncolored map determined by the original hypothesis or by the proof?
If the proof determines the shape of the map, then:
A. Doesn't knowing the shape of the map give some information? (Therefore not Zero Knowledge Proof)
B. Would an alternate coloring (assuming one exists) be an alternate proof?
C. If I can color the map can would it mean that I also have a proof?
D. Assuming that I have verified the coloring in your supposed proof, how do I know that it links back to the original hypothesis as opposed to a random 3 colored map?
If the shape is determined by the hypothesis then i guess it answers most of the questions above.
2. Every finite map either can either be 3-colored or not. If yes then you have proved the hypothesis, if not then the hypothesis is false.
A. What about an unprovable hypothesis "Gödel's incompleteness"? Will it also have a map? If so will it be 3-colorable or not?
Something he rather glosses over is just how quickly these maps grow with the complexity of the problem. Even an apparently “simple” proof, say that there are infinitely many primes, balloons to a very large number of strictly formal statements, and hence a very large map.
Who cares. Show us anyway.
Yes. You have to start with the absolute basics. You even have to construct natural numbers from scratch (see Peano arithmetic). I think he kind of misrepresented the complexity by saying converting statements to maps is a "simple" translation
This video makes sense for how zkps work in practice. Assuming large maps and then sampling that maps borders to get 99.99999999% confidence.
- I can solve this sudoku
- Prove it
- Sum of numbers in 4th row is 45
This guy just won the Turing award!!! 🎉🎉🎉
Avi won the Abel Prize this week, and May sees the 50th anniversary of Stephen Cook's landmark 1971 paper which demonstrated NP-completeness.
Should this video have been uploaded to the main channel?
What’s the difference? Why is there a “main” channel and a “sub” channel?
@@codycast Numberphile2, since the secondary channel.
@@codycast This channel is for the longer and more in depth bits that the main channel cuts for the sake of being more accessible.
@@biometrix_ yeah but what’s the point? Why not Numberphile 3, and 4, and 5, and...
/me hums... "I'm so dizzy, my head is spinning
Like a whirlpool, it never ends
And it's you, Avi, making it spin
You're making me dizzy"
ty for posting! :)
I just love his accent! The way he pronounces pwoof has some nice charm to it.
His accent is not effective for an English speaking audience. He has a lot of trouble enunciating.
It would be interesting to see a discussion of what proportion of published proofs are incorrect.
Plot twist, I didn't know what an envelope is so you teach me something
-You know nothing.
-Correct.
However, now you know that you know nothing, therefore the statement is false and the fabric of reality is torn apart due to the paradox.
This has been the best numberphile in a long time.
It's humbling to catch a brief glimpse of Avi's brilliance
This was great! Should have been numberphile 1 content.
I think this was one of numberphile’s best videos. I thought he explained it very well.
The real question is what is the Zero Knowledge Proof of the Zero Knowledge Proof proof.
🤔😳🤯
First thing I thought when he said they proved it
This sentence is false.
As he first said, it's interactive. Can't be reduced to pure logic.
If you take the statement discussed in this video regarding the ability to convince a verifier (with as close to 100% certainty as you desire) that a map is 3-colorable, by only revealing random pairs of neighboring colors chosen from a random permutation of such a coloring, then that statement can be converted into a map.
And that map would be, according to the video, 3-colorable. And you could convincingly demonstrate that the map is 3-colorable without revealing any information, using the same method.
I believe this is what you're looking for.
It's moments like these when you feel the beauty of mathematics and formal logic. When it truly shines.
You can have a cake and eat it. Er... I mean, you can have a proof and not tell it in details. And it still works. *convincingly shows why*
"But I want to know the proof."
"You don't need to know the proof. Here's the proof you don't."
"I don't need to know the proof."
It has the beauty and style of a Jedi trick, only with a solid mathematical ground under it.
Does anybody know what happens to undecidable statements when you construct their equivalent 3-color map? Whether a map is 3-colorable or not seems to me to be always either true or false, but Godels incompleteness theorem (also referenced) would seem to imply some maps are neither. This NP stuff on proving is super interesting but indeed the video left me with many more questions!
I THINK it works like this:
The colorings encode proofs of statements.
For a statement X and a map MX, the existence of a 3-coloring for MX is equivalent to a proof of X.
The negation ~X has a map M~X and a 3-coloring for M~X corresponds to a proof X is false.
If X is undecidable from your axioms that means there is no proof of X nor a proof of ~X. Equivalently there is no 3-coloring of MX nor a 3-coloring of M~X
Undecidable statements are not in NP so they cannot be converted into a map
This is so interesting, I feel like I get the main point but now I'm really interested in the algorithm that transforms proofs into maps and vice versa and *how/why* it works. these connections are so interesting and beautiful, it makes me want to become a mathematician
You should ! The topic is super interesting, I'm not sure how much they would teach it in math tho, as it is more central to more computer science things
mark van dijken You and everyone else too! I hope they eventually reference some course or lesson on the topic. I don't need a concise 30-min video. I'd gladly speed weeks getting into it.
How do you verify that the map was actually generated from the proof algorithm and isn't some completely unrelated three-color map?
You as a verifier could generate the map yourself from the statement that is supposedly proven, then tell the prover to color it in. Or convert the map back to the statement and check they are identical. The map and the statement are the same thing in different forms and can be translated perfectly back and forth.
Then you can verify that the coloring is actually valid (only three colors used and no neighbors the same color), either by just looking at it and checking it, or alternatively if the prover is paranoid and don't want to let you steal the proof, by the zero knowledge (envelope) method. Then you know that the statement is true.
Same way you verify if a real infinite Penrose Tiling is not identical to another real infinite Penrose Tiling. xD
I don't comprehend - in the example with the map I can fake a proof that I can color any map with just 2 colors. Because when the verifier ask me about any two neighboring countries, I'll always show two different "random" colors.
Ahh the legend wigderson!! Jealous of all my Princeton friends who have the pleasure to learn from him
This video is the first time I've seen him, and I'm not impressed.
Regarding an example, I did zero knowledge proofs at University, and we did one example, which was graph isomorphism, which was really hard to wrap my head around. The lecturer then said every other example is vastly too complicated to be covered in the course. And because the only example within the scope of the course is graph isomorphism, it won't be on the exam haha.
What about Gödel’s Incompleteness Theorem? If that says that there are statements that cannot be proven to be either true or false, and NP completeness says that every statement can be converted into a map, there must then be maps where it is impossible to find a colouring, but also impossible to prove that there isn’t one. Would these maps be infinite, or how does this work?
I like this insight. I'm not sure if that is the correct analogy, but I'm also not sure that it isn't the correct analogy! Either way, I like it!
The way I believe it works is as follows.
Let's say you have a statement X.
There is a map called MX.
If there exists a proof of X then MX can be colored with 3 colors. A specific proof is a specific coloring.
If X is false then that means ~X ("not X") is true.
There is a map M~X. If there is a proof that X is false, i.e., a proof of ~X then there is a coloring of M~X.
If X is undecidable then there will not be a proof of X nor a proof of ~X and so neither MX nor M~X will have a 3-coloring.
These maps cannot actually tell you anything about the inherent "truth" of various mathematical statements. They can only encode the existence of proofs following from a specific set of axioms.
Gödels theorem then basically says that for any system (e.g. Peano arithmetic, or ZFC) there will be some statement X that can be encoded in that system, and thus for which we can construct a map MX, but for which both MX and M~X won't have a 3-coloring.
Sorry to clarify, there will be an X we BELIEVE to be TRUE that can be encoded in the system but for which there doesn't exist a proof (coloring) of X nor of ~X.
But what about unverifiable statements? Can these be translated in a 3-coloring map problem? Why does it not contradict Gödel's incompleteness theorem?
Only formal systems of sufficient expressivity are incomplete. Less powerful ones are complete. Since satisfiability of boolean formulas is an NP-complete problem, I'm guessing that the formal system involved is boolean formulas which are (syntactically) complete and thus wouldn't allow you to express unverifiable statements. No boolean statement -> no map.
@@AubreyBarnard what you say must be true, but he was giving examples from numbers or higher logic, not just propositional logic. So either his exposition is misleading, or there is something I don't get. The way he puts it, it looks like Godel's incompleteness is violated.
AFAIK the colored map represents both the statement and the proof. Unverifiable statements does not have a proof, thus there exists no colored map for them.
I have the most wonderful proof of the zero knowledge proof, but it’s a bit too large to fit within this TH-cam comment.
I'll come back in 300 years
The humour in this comment is marginal
@@trueriver1950 yeah, it's a stale fermat.
HAHAHAHAHA Too accurate :,)
👌🏾👌🏾👌🏾 to all commenters.
I didn't understand anything, but he proved to me it's an important video. No knowledge transfer happened!
Still can't wrap my head around that you can convert those proofs into those three color maps... gives me a headache
RIght? I'm so interested in the specifics. Like whats the simplest statement you can convert, and can you please draw it and explain how it captures the statement?
@@Android480 tattoo, the map for the statement that all statements can be expressed as maps.
@@Android480 i failed to find some sort of converting tool for that. i would really love to see some simple demonstration
Wonderful video about ZKPs, thank you so much Avi and Numberphile!
Do you think im going to spend 33 minutes in a math video?
Of course i am
Given that some people would spend that time...arguing with people on the internet who won't change their minds, watching so called reality TV, doing drugs, getting drunk, or reading 50 shade of grey, I think you can easily justify the 33 minutes vs those actions :)
You have 33 likes..I can't spoil that.
I believe this has been a zero-knowledge proof of zero-knowledge proofs.
Because I watched the whole thing and I still have zero knowledge.
It would be nice if he could come back and explain how they translate statements to maps
The four-colouring of the heart on the whiteboard is a nice touch :D
You: I have a zero knowledge proof of this problem.
Hacker: Tricks you into opening NOT neighboring envelops in order to discover the whole map through finding envelops with the same color.
Oh dang! Permitting that kind of query would undermine the whole process.
Identity thief: changes the contents of the envelopes after you pick which pair to open.
Except...the color scheme can be shifted (1 of 6 variations I think was mentioned) randomly. You could repeatedly query until every 'country' on the map was revealed...and still not know what the final answer/3-coloring of the entire map is. Hence the term 'zero knowledge'.
@@ckshreve We're not interested in the colors themselves, any more than we care about whether we call a variable x or y. A given color is just an abstract label. What we are interested in is the structure of the coloration, which directly corresponds with the structure of the proof we want to find out.
@@ckshreve if we verify three countries A, B and C are different colors we can color the rest of the map using A B and C. Youd just need to cycle through them till theyre the same color
Can this be inverted? Meaning, go from a map to a set of statements? Because it would be fascinating to create arbitrary maps, find a 3-coloring, and then know to what problem I just found a solution!
Also, since there are statements that are true but cannot be proved to be true, are there maps that are 3-colorable that can't be colorable? I am facinated, but seems like a lot that's needed to understand here.
Drinking game: take a shot every time he says proof
Awesome video. Makes me want to learn about formal logic. Thank you!
Doesn't this mean that every mathematical statement is, in principle, provable or disprovable? Doesn't this contradict Gödel's incompleteness theorem?
in the subject's spirit: no
If I understood the video correctly, it is not. If you have an improvable statement and translate it to a map, the map wont have a three coloring. But if you have a non-3-colorable map and translate it to a statment, it will only tell you, that there is no prove to the statment, not that it is false.
@@tth-2507 so you could use it to prove there is no proof? (correct or not)
@@AbelShields I would say yes. But persumably thats hard ... mind that to show that it is unprovable you additionaly would have to show that you also cant disprove your statement.
@@tth-2507 Proving there is no three colouring is in principle easy (but slow); you just have to search all colourings. You can similarly show that the negation of the statement has no three colouring, and hence no proof.
How is the secret envelope mechanism implemented in practice? I know you can use a cryptographic commitment scheme. To a casual viewer though, that's kind of an important detail. A lot of schemes are possible if you're allowed to assume magic.
If "we tried to prove you wrong a buncha times, and couldn't" worked as a proof-of-proof, we can "prove" that someone has a proof to the Collatz Conjecture.
Imagine someone hands me a proof of the Collatz conjecture. There's 2 ways I could try to prove them wrong:
A) Shred the proof they handed me. I don't need that. Then guess a random number and run it through the Collatz function a bunch of times until I reach 1. Repeat many times.
B) Flip the proof open to a random page and check if the author made an error in reasoning on that page. Repeat many times.
I'll never be too certain that the Collatz conjecture is true by doing A. But if I do B, pretty quickly I'll have checked every page in the proof, and will be fairly certain that the proof is correct. (Or will have found an error if it is false.) Zero knowledge proofs look like B, not like A. (Just with weird-looking "encryption" of the proof.)
@@phillipb8765 ah, that makes more sense. Thank you.
I think the idea is
The map would always be 3colorable no matter what, but if you had a proof, and put it into algorithm, then the result would be a completed valid 3 coloring of that map.
And not that, say, it could be reversed. Or that you could know right away if a statement was provable, by looking at the map and finding it could not be 3colored.
Crypto is all about that, how can you in encrypt/decrypt, while everyone is listening, without giving out either keys.
Or to make sure a chain of information is validated, without knowing the original source.(crypto currency).
The warning "Do not erase on the board", proves that someone erased it.
+
So basically, if the proof is correct then the map that represents it is 3-colourable, and if the proof is wrong then there will be at least one space that is touching all three colours. And you can ask questions about regions on the map, like "Is X touching Y?" or "Are X and Y the same colour?" But there are 6 possible colour schemes for the map that are otherwise identical but for the order of the colours, and the person with the map can palette-switch between them at will. For instance, you find out 1 and 3 are not touching each other and are told they are both blue (but they could also both be red, or both green); 2 and 4 are not touching and they are both blue; but when you ask about 1 and 2, they might be touching and one is red, the other green, then 3 and 4 are not touching and are both blue .....
The person with the map can avoid giving away enough information to allow you to reproduce the map yourself, because you only know "same or different"; but there are still two equally-likely kinds of "different", and the map holder can switch between possible colour schemes from one question to another and so prevent you from fully recreating the map; for instance by claiming every non-touching pair to be "both blue" and every non-touching pair to be "one red, one green". This way, you can be presented with an impossible composite of the six equivalent maps.
If the proof is wrong, their map will have two regions of the same colour that are touching; and the map is finite, so if you keep asking questions long enough, you are bound to turn this fault up eventually -- "touching, blue and blue" probably! But the more questions you ask without finding a colouring violation, the greater the confidence you can have that the map _is_ three-colourable, even although you can never properly recreate the entire map at once because the holder seems to insist every region in it is blue .....
What does the three coloring of the four color theorem look like
nice idea for a tattoo
I have to echo what everyone is requesting:
It would be AWESOME to do a follow-up video of an example translating a theorem into a Map (ideally a super simple theorem, even "trivial" like 0+1=1 or two parallel lines don't cross )
The power of such a mathematical tool is immense!
(I wonder if there are ways to translate theorems into different Math problems, say changing the "theorem" 2+2=4 into a polynomial function and if there is exactly one x-intercept then it is true. Maybe Colour-map translation is only one way to do this, and there is an infinite number of ways to do this, some more efficient than others. Thinking further, maybe there is a tradeoff between ease-of-translation and ease-of-resolution, defined by an equation relating the two.)
So does this imply that anyone, given enough time, should be able to prove any provable mathematical claim?
This is true regardless of the mapping theorem. If you have enough time you can type every possible document using every possible symbol, and that would include the proofs to every provable mathematical claim (and would also include my grandmother's telephone number or the number of ways a monkey can scratch its bottom)
@@TommasoGianiorio That's an interesting observation
It almost seems as if there should be some way to generate random 3-colored maps and then reverse engineer them to declare random proofs. I assume there are infinite many possible 3-colored maps, and therefore infinitely many mathematical proofs? Or are there just infinitely many variations of the same proof? ie infinitely many ways to demonstrate that AxB = BxA
import random
print(random.sample('rgb', 2))
I didn't understand how he is caught cheating if he doesn't have a proof for a three-colour map problem?
If he has proof, the two colours will be randomly chosen from the 6 permutations. This leads me to believe that we won't have random combinations if he cheated and so he can be caught with near 100% probability by quizzing him a million times. But I don't see how the combinations are not random when he cheats. Can someone please help me make this connection?
Being caught cheating would mean opening an envelope and finding a fourth color or opening two adjacent ones and finding the same color in each. Both of those scenarios would prove 100% that the prover doesn’t actually have a proof. The randomness of the colors isn’t what verifies the proof. The point of the randomness is just to make sure no information is conveyed.
The piece I’m missing is core to the “zero knowledge” principle - how answering a single “any two envelope” question proves anything - if the answer could have been provided by the asker, how does it prove anything? i.e. if I can answer with any two random (different) colors, how does that convince the asker anything at all?
Afaik (after watching this video), the reason for this is, that the prover fixates all colors (the whole map coloring), before knowing which neighbours are chosen.
Maybe it's easier to understand if you split the process into 4 steps,: (1) for each country (map tile) the prover gives the verifier a sealed envelope with the color of this country. In total it's a 3-coloring of the map, but sealed so the verifier can't see them. (2) The verifier asks for two neighbouring countries. (3) The prover provides the keys to unseal the envelopes of these two countries. (4) The verifier unseals those two envelopes and checks if the colors are distinct.
So in essence, the prover encrypts a 3-coloring and then the verifier is allowed to decrypt two tiles of their choice. Because it is fixated, the prover can't just provide 2 random distinct colors (only a random coloring of the complete map which likely includes neighbouring tiles with the same color)
@@aapianomusic Yes, after rewatching the video, you are absolutely correct. I neglected to consider that the two countries in question aren't known ahead of time to the prover, so they have to provide valid pairs of colors for ALL pairings of neighboring countries, not just a single pairing. Thanks for your comment.
@@TheJonHeese You still are onto something that was not clear in the video though. The colouring is claimed to be fixed at the start, but Avi makes it clear that if he actually showed you the real colours each time you open the envelopes, then he's revealing the proof more and more with each pair you open. The way it becomes zero-knowledge is that Avi is actually allowed to permute his colourings each time you ask (and he's also allowed to refuse to answer some questions, which is another issue that could lead to the proof being unsatisfactory). If he's changing the colourings each time, then it's not fixed. So if you choose three countries that all border eachother 1,2,3, and want to know if they are all different, then you might test 1&2 then 2&3 and then 1&3, the results should all be distinct. However, since Avi is allowed to change these before hand, then how can you know that he's just permuting them (which would be a valid proof, since permutation doesn't affect the proof) and not simply changing his answers each time so that he never contradicts you. You can't compare colours you learned from two different tests, so you can't catch him out by using information from 1&2 (say red&green) and 2&3 (say red&blue) to conclude that there was an error... I suppose there is a mathematical way to prove when the answers you've been given can't possibly be a valid permutation, but naively it seems like Avi could just respond 'red & green' to every question and "prove" that all bordering countries are distinct.... you need some way to fix the colouring AND fix the permutation process so that you know Avi is actually consistently describing this map...
@@sfreer6044 the idea is that, if he has a valid 3-colouring, no 2 neighbouring envelopes that you pick will EVER have the same colour (regardless of if he permutes between guesses, and regardless of how many envelopes you check), whereas if he doesn't have a valid 3-colouring, you are likely to eventually (after an arbitrarily large number of picks) stumble onto a pair of neighbouring envelopes that do contain the same colour, which would imply that he didn't have a 3-colouring.
@@cheeseburger118 yes, but if he doesn't have a 3-colouring why can't he still just consistently make up pairs of different colours to always pass? I assumed it would be because the answers need to form a self-consistent pattern, but this would eventually add up to give the colouring. Without any need for consistency between responses to the 2 envelopes, why not just say "red and blue" everytime and never fail, but never prove anything? I'm missing what stops this exploit from working.
17:26 does the agent asking the questions always have to inquire about two neighbouring countries? If he doesn't, he could in O(M!) time uncover the exact colouring of the prover, where M is the maximum numbers of colours used. M is very low compared to the number of countries, so it would even be efficient to reconstruct the colouring
He said in passing if the countries were not neighboring then prover didn't have to answer at around 31:45 . But even if the prover did, I think it still would be zero knowledge. The question here being "could you simulate the interactive proof by yourself". And I think the answer is yes as new, independently chosen permutation of colors are put in the envelops in each round.
So he says "simple" a lot. I'm not sure his idea of simple aligns with mine :)
I was thinking about whether I should give up half an hour to watch a mathematical video (I'm not a mathematician) and I should say that I do not regret my decision. The result is quite amazing.
How does this relate to goedels incompleteness theorem? How would the map of an undecidable statement look like.
No map exists for undecidables, the algorithm specifically only works on provable theorems
@@MrRyanroberson1 it can't only work for provable statements, because it also works for false statements.
@@Danicker by provable i mean possible to prove an answer to, yes or no. also you could just negate it and prove the negative (instead of proving A is false, prove not A is true)
@@MrRyanroberson1 Okay fair enough, but I think 'decidable' is a better term.
@@MrRyanroberson1 But what would happen if try to use this technique to prove a mathematical statements, because I cannot know a priori if the statement is decidable. Since any mathematical statement can be encoded with 3-Sat(Not sure if its 3-sat, or sth different), It should also be possible to encode undecidable statements and then use a prover to get a proof for it. Ofc such provers don't exists atm as far as I know
I think his story of triumph over his (John Nash) schizophrenia is the most inspiring aspect of his achievements.
What would the map be for the mathematical statement of "This statement is false."?
+
If I had to guess, there is none, because statements in mathematics are not allowed to self-refer (specifically because it results in such paradoxes).
Unfortunately "this statement is false" isn't a mathematical statement. It's a linquistical paradox, but not a valid mathematical statement.
@@thegreatdream8427 Just because the mathematics community 'doesn't allow" people to do it doesn't affect whether or not you can construct a graph of it, but there is might be some more rigorous reason why that is the case.
@@MK-13337 The statement itself may be in English, but I was referring to the mathematical translation of that statement. I don't believe it is a linguisticall paradox, it is just the method I used to communicate the vague notion that "I am wrong". I don't see a reason why you couldn't write it mathematically.
so mind readers
(who guess the card. number, etc)
can prove that they have a magical power to read minds
using zero-knowledge proofs
In fact, they do it every day. It is their job.
Well, if you a suffiently efficient way to create a non-perfect 3 colored map with some small error, you could fake your way out with the same error. Does this mean that to have a certitude of 99.9999%, and if you know faking it has a error of around 0.00001%, you would need to probe around 10^13 times? And if you don't know how efficient a faking algorithm is it's basically pointless?
The only thing that really bothers me is that the zero knowledge proofs rely on inductive reasoning rather than on deduction (they are not “proofs” in the usual sense but rather provide “proof” in the sense of evidence). I guess the goal is just to attain “conviction” in the verifier but was anyone else bugged by this? Thanks I’d love to learn more
Why is this not on the main channel?
Probably too dense.
I love that Brady asks questions a person with no knowledge would ask
I think u did it, you zero knowledged proved the zero knowledge proof cause I walked away from this video with no new knowledge on the topic
What part didn‘t you understand? In short: every statement can be converted into a map. Every proof (true statement) is a 3-coloring of that map. If I show you a three coloring of the map I have given you a proof (indirectly), as everything can be converted back to mathematical statements. But wait because I showed you a specific coloring I also transmitted information. In order to make it zero knowledge you get to ask me 2 neighbouring countirss of the map, which I colored in before you asked. If they are opposite you‘re a little bit convinced. Now I color it again in a different way and let you ask me again. If they‘re opposite again you‘re be a little more convinced. Ok we repeat this until you‘re 99.999...% sure I really do always color the map with a 3 colors.
@@screwhalunderhill885 thank you for the "too smart/wordy didn't understand"
Feels like that's not even a proof because... You're getting information in the form of a limiting process...
Like when do you declare it's true - 75%? 99.99999%? Feels arbitrary
_i guess you gave me a no knowledge proof_
This video stays true to its content. I have watched the whole video and still learned nothing about the process of zero knowledge proof.