作者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