推 revivalworld:NP 完備確實不能說最難的 可是原本的問題是要對非本 06/01 22:04
→ revivalworld:科系的人說明這是什麼 所以這樣說簡單又直接 至少 06/01 22:04
→ revivalworld:這也是世紀大難題 我是這樣想的啦= = 06/01 22:06
: 推 revivalworld:就說是宇宙中最難的問題就好了 http://0rz.tw/1e15R
NP-Complete 的問題不可能是宇宙中最難的問題，雖然目前計算它是需要不少時間，
但至少 NP-Complete 的問題是可以計算的(decidable)。
還有一大堆問題是根本不能計算的(undecidable)，例如 halting problem 。
當然這邊的「可不可計算」是指用 Turing machine 而言，並非代表無解。
--
我實實在在的告訴你們，一粒麥子不落在地裡死了，
仍舊是一粒，若是死了，就結出許多子粒來。
約翰福音 12:24
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.248.178.71