作者sitos (麦子)
看板ask-why
标题Re: [请益] NP Complete
时间Sun Jun 1 19:42:24 2008
: 推 revivalworld:就说是宇宙中最难的问题就好了 http://0rz.tw/1e15R
NP-Complete 的问题不可能是宇宙中最难的问题，虽然目前计算它是需要不少时间，
但至少 NP-Complete 的问题是可以计算的(decidable)。
还有一大堆问题是根本不能计算的(undecidable)，例如 halting problem 。
当然这边的「可不可计算」是指用 Turing machine 而言，并非代表无解。
--
我实实在在的告诉你们，一粒麦子不落在地里死了，
仍旧是一粒，若是死了，就结出许多子粒来。
约翰福音 12:24
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 60.248.178.71
1F：推 revivalworld:NP 完备确实不能说最难的 可是原本的问题是要对非本 06/01 22:04
2F：→ revivalworld:科系的人说明这是什麽 所以这样说简单又直接 至少 06/01 22:04
3F：→ revivalworld:这也是世纪大难题 我是这样想的啦= = 06/01 22:06