作者joeyeh (joe)
看板puzzle
标题[请益]请问有人知道关於各类魔方的零知识吗?
时间Thu Oct 16 20:48:15 2008
10月的科学人有介绍到关於零知识zero knowledge的匿名认证,
网路上有关於零知识数独读文章
不知道有没有人写有关於魔方的零知识文章?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.118.68.11
1F：推 aegius1r:可以解释一下零知识吗@"@? 10/16 23:15
2F：推 LPH66:基本上零知识证明要能有用是在所谓「难」的问题才行 10/17 00:59
3F：→ LPH66:这里的「难」严格说起来是所谓的NP完全问题 10/17 01:00
4F：→ LPH66:解(任意大小的)数独已经被证出来是NP完全 10/17 01:01
5F：→ LPH66:但建立魔方我还没看到任何说它是NPC或什麽的叙述 10/17 01:02
6F：→ LPH66:(毕竟我们有一个建立魔方的半公式解) 10/17 01:03
7F：→ joeyeh:各类? 所有每一种类都有半公式解? 那应该就没有了 10/17 07:38
8F：推 LPH66:唔 我是指要产生一个某个大小的魔方.... 10/17 08:29
9F：推 puzzlez:难道不能用z-k来证明一个人会解魔方吗？ 10/17 10:18