作者LPH66 (-858993460)
看板CSSE
标题Re: [问题] halt problem 是无解还是NP-hard ?
时间Mon Nov 1 16:02:31 2010
※ 引述《LFking (小均)》之铭言：
: 感谢大大的回答,
: 但NP-hard是否也包含 无解的问题 ？
: 所谓的NP不就是 有解的题目 但要花很多时间（指数时间）？
是的
NP-hard 虽然叫这个名字 但它并不是 NP 的子集
维基上的图应该很清楚的表示了这一点:
http://en.wikipedia.org/wiki/NP-hard
http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg
你可能是把 NP-hard 和 NP-complete 弄混了
NP-complete 才是 NP 的子集 它正是 NP-hard 和 NP 的交集
--
"LPH" is for "Let Program Heal us"....
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.28.92
1F：推 LFking:感谢！ 受教了！ 11/06 20:31