ACM通信
最后一个字节
新贵谜题:证明而不教学/教学而不证明
神奇的沙子计数器声称，只需要观察桶里的沙子就能知道里面有多少粒沙子。你相信他吗?
图片来源:Andrij Borys Associates / Shutterstock
彼得·温克勒(Peter Winkler)在数学上很优雅，经常是异想天开的谜题，读起来和玩起来都很愉快。我的专栏现在走上了一条不同的道路。每一个都将分为两部分:一部分是可行的，我将为此提供一个解决方案，另一部分是一个“暴发户”，或傲慢的变体，我不知道如何解决，这将是社区的一个开放问题。我们开始吧。
“零知识”证明需要在某人(证明者)断言一个命题和另一个人(验证者)确定它是否正确之间进行交互。证明为验证者提供了零知识，因为验证者除了知道陈述是真实的以外，没有获得任何知识，无论是绝对的或排除合理怀疑。1所讨论的陈述通常是数学性质的，但在这种情况下，它就像，嗯，小儿科。
没有发现记录