[請益] 請問有人知道關於各類魔方的零知識嗎?

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (joe)時間17年前 (2008/10/16 20:48), 編輯推噓4(405)
留言9則, 4人參與, 最新討論串1/2 (看更多)
10月的科學人有介紹到關於零知識zero knowledge的匿名認證, 網路上有關於零知識數獨讀文章 不知道有沒有人寫有關於魔方的零知識文章? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.118.68.11

10/16 23:15, , 1F
可以解釋一下零知識嗎@"@?
10/16 23:15, 1F

10/17 00:59, , 2F
基本上零知識證明要能有用是在所謂「難」的問題才行
10/17 00:59, 2F

10/17 01:00, , 3F
這裡的「難」嚴格說起來是所謂的NP完全問題
10/17 01:00, 3F

10/17 01:01, , 4F
解(任意大小的)數獨已經被證出來是NP完全
10/17 01:01, 4F

10/17 01:02, , 5F
但建立魔方我還沒看到任何說它是NPC或什麼的敘述
10/17 01:02, 5F

10/17 01:03, , 6F
(畢竟我們有一個建立魔方的半公式解)
10/17 01:03, 6F

10/17 07:38, , 7F
各類? 所有每一種類都有半公式解? 那應該就沒有了
10/17 07:38, 7F

10/17 08:29, , 8F
唔 我是指要產生一個某個大小的魔方....
10/17 08:29, 8F

10/17 10:18, , 9F
難道不能用z-k來證明一個人會解魔方嗎?
10/17 10:18, 9F
文章代碼(AID): #18zpWGcu (puzzle)
文章代碼(AID): #18zpWGcu (puzzle)