作者waynetooni (wegogo)
看板Grad-ProbAsk
标题[理工] 107中央资演
时间Sun Jan 20 11:06:11 2019
https://imgur.com/kn5Zk79
想问一下16题的A选项
problem X 有 ND algo 不是就代表X是个NP问题吗?
但是这选项却不能选
我在猜是不是因为NP-complete也有ND algo
但NP-complete是NP和NP hard的交集
所以有ND algo的problem也有可能是 NP hard problem
请问这样想是正确的吗?
先谢谢各位神人了~
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.249.53.64
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1547953573.A.062.html
1F：→ krusnoopy: 是不是答案给错啦XD 我没理解错的话 有ND poly解法的 01/20 11:49
2F：→ krusnoopy: 就是NP 难道他强调要说精准一点:"这可能是P" 01/20 11:49
3F：推 eric131204: P也包含於NP啊 应该对吧 01/20 13:47
4F：→ eric131204: 况且这不就NP的定义？ 01/20 13:47
5F：推 skyHuan: 答案是谁给的... 01/21 01:15