[理工] 107中央资演 waynetooni PTT批踢踢实业坊

[理工] 107中央资演

楼主: waynetooni (wegogo) 2019-01-20 11:06:11

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
请问这样想是正确的吗?
先谢谢各位神人了~

作者: krusnoopy (push) 2019-01-20 11:49:00

是不是答案给错啦XD 我没理解错的话有ND poly解法的就是NP 难道他强调要说精准一点:"这可能是P"

作者: eric131204 (暗女巫) 2019-01-20 13:47:00

P也包含于NP啊应该对吧况且这不就NP的定义？

作者: skyHuan (Huan) 2019-01-21 01:15:00

答案是谁给的...

继续阅读

Re: [理工] 100台大数学jwlhs104 [理工] 100台大计系kaidi620 [理工] 103成大程式设计st474ddr [理工] 计组的问题重要观念kaidi620 [理工] 100台大电信线代fmtshk [理工] 特征值奇怪求法cvn21 [理工] 107台科OS第5题Hertzfeld 107中央资演wilson50101 [理工] 107交大资结AAQ8 [理工] 105交大资结AAQ8