4 ms·
Yeah, this article tries too hard to appeal to all audiences in a way that ends up making it confusing for everyone. Starts off with the clumsy maze example, th
by PeeMcGee 4y ago
Yeah, this article tries too hard to appeal to all audiences in a way that ends up making it confusing for everyone. Starts off with the clumsy maze example, then hops over into graph theory and NP-complete proofs, then hand waves something about sharing bits and quantum computing... But enough about that, it turns out blockchain will prevent nuclear war!
- elondaits 4y agoAnd they lost me with the graph example… because both graphs are the same! How are you not leaking information about the solution if you’re showing the path in the exact same graph! If they consider two graphs drawn differently as different graphs, they should clarify it from the start … and maybe not pose it as a graph problem.
- junofan 4y agoImagine the graphs are really, really big. Graph isomorphism is NP-hard. Alice gives Bob a graph. Bob can ask Alice to show the bijection (hard) or show a path (hard) but not both. Say Alice and Bob do this 40 times. Can you see how Bob should be convinced that Alice is giving him isomorphic graphs and that she knows a path through the graph? Otherwise Alice would have failed to answer one of his questions along the way.