[理工] 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