You mention that this problem has overlap with training neural nets. Could you link some further reading for this? :)
Show HN: I made a puzzle game that gently introduces my favorite math mysteries
151–160 of 177 posts
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#152Would be nice to Introduce another continent like Europe :) it looks really nice tho!
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#153> Warning: very difficult! Skip after trying a lot. I think "very difficult" is misleading here. It implies there is an answer if you try hard enough.
i appreciate the intention to let you struggle with it on your own for a bit, but not go crazy.
a better experience might be having the warning reveal more after a few attempts, but I don't mind starting with a "warning it's surprisingly tricky"
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#154Earlier quoted context omitted.
I've got another problem about this zero knowledge proof. The digital version doesn't make a lot of sense to me. It depends on the fact we don't have a fast integer factorization algorithm. But integer factorization is not proven to be NP-complete, and 3-coloring is NP-complete. So isn't it possible that there is a polynomial time algorithm for integer factorization, but no polynominal time algorithm for 3-coloring,…
I think you're right, and integer-factorization is often used in these examples as a process that is hard to do but easy to verify. There are plenty of other processes that could be substituted in, e.g. reversing SHA256 hashes, that would likely be even less tractable to the target audience. However, if P = NP, there is no process that works here - there's nothing that is hard to do but easy to demonstrate, and there…
> However, if P = NP, there is no process that works here - there's nothing that is hard to do but easy to demonstrate, and therefore no zero knowledge proofs exist.
IIRC technically, there are zero-knowledge proofs for all statements in P: the proof is "prove it yourself", which the verifier can do because it's in P.
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#155Well done, enjoyed this a lot.
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#156Nice puzzle, congrats!
I also like this part of maths, and there's a related concept of Snark graphs.
https://en.wikipedia.org/wiki/Snark_(graph_theory)
First is that "One of the equivalent forms of the four color theorem is that every snark is a non-planar graph". Second, is as strengthened form of the four color theorem: "every snark has the Petersen graph as a minor", which is kind of proven (already 25 years ago), but still lacks 1 paper: https://thomas.math.gatech.edu/FC/generalize.html https://math.stackexchange.com/questions/3692582/what-is-the...
And another related concept is of nowhere-zero flows, and even more stronger conjecture that "every bridgeless graph with no Petersen minor has a nowhere zero 4-flow". https://en.wikipedia.org/wiki/Nowhere-zero_flow
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#157Earlier quoted context omitted.
Torus, of course, but how does that relate to enclaves, which are planar ?
You might want to colour the exclave the same colour as the rest of its country, even though no connection can exist between them on the plane.
It seems like you're using "enclave" and "exclave" interchangeably, which is causing confusion. What you're referring to is an exclave; an enclave is when one region is completely surrounded by another, like Lesotho or Vatican City.
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#158Earlier quoted context omitted.
The best analogy of zk-proofs I've heard is to suppose you have found Waldo in "Where's Waldo," and want to prove that you have done this without revealing the location. You could take a piece of paper (much larger than the picture/book), and cut out a waldo-shaped hole it and position the paper such that he is shown in the hole. Then, when you show it to the challenger, they know that you have found him without you…
But it's a simplification: One iteration is enough to detect lying. In a real ZK proof the probability of the prover lying reduces after each iteration but never reached 0.
there is a probabilistic interactive component. this protocol allows the prover to fake it by just using a book where they know where Waldo is. in each iteration you choose whether to confirm it's the original book and page under the paper or see Waldo (but not both). a cheating prover has p = .5 of fooling a verifier.
but your concern is invalid to begin with. nothing in the definition of a zkp requires them to be multi-round interactive. there exist non-interactive zkp.
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#159Earlier quoted context omitted.
The best analogy of zk-proofs I've heard is to suppose you have found Waldo in "Where's Waldo," and want to prove that you have done this without revealing the location. You could take a piece of paper (much larger than the picture/book), and cut out a waldo-shaped hole it and position the paper such that he is shown in the hole. Then, when you show it to the challenger, they know that you have found him without you…
How do I know if it is the original "Where's Waldo" under the paper?
in each iteration you choose whether to confirm it's the original book and page under the paper or see waldo
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#160Earlier quoted context omitted.
The best analogy of zk-proofs I've heard is to suppose you have found Waldo in "Where's Waldo," and want to prove that you have done this without revealing the location. You could take a piece of paper (much larger than the picture/book), and cut out a waldo-shaped hole it and position the paper such that he is shown in the hole. Then, when you show it to the challenger, they know that you have found him without you…
I think that conveys what a zero knowledge proof achieves but it doesn't really correspond to any real zero knowledge proof algorithms. You can't do that over the phone, which is kind of the whole point.
no, that's not even close to the whole point. the analogy is to introduce the concept of proving something to a verifier without giving the verifier the solution
the paint-mixing analogy of diffie-hellman also can't be done over the phone, but it helps people understand how a shared secret can be established even if all communication is intercepted