3 ms·
And 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
by elondaits 4y ago
And 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.