[理工] 演算法 NP-complete yorunohoshi PTT批踢踢實業坊

[理工] 演算法 NP-complete

作者: yorunohoshi (夜の星) 2016-11-23 14:49:49

http://imgur.com/a/71WoR
大家好想請問這題的第二小題
我的理解是：
所有的NP問題都可以reduce成NP-complete的問題
因此只要找到一個polynomial time的Algo可解NP-complete 則NP問題皆可在多項式時間解
那第二小題錯的原因是因為
有可能是某些NP(or NP-complete)問題在轉換時需要O(n^4)以上的時間嗎？
這樣NP問題都可以在多項式時間內解，只是某些不一定被bound在O(n^3)？
不知道這樣解釋對不對@@ 想請教大家想法謝謝~

作者: aa06697 (todo se andarà) 2016-11-23 17:28:00

個人想法跟你一樣多項式時間可解未必都一樣大 n 跟 n^100 差蠻多的

作者: PTTleader (PTT領導) 2016-11-23 18:46:00

所有的NP問題都可以reduce成NP-complete的問題??沒事

作者: yorunohoshi (夜の星) 2016-11-24 10:16:00

了解了，感謝a大～

繼續閱讀

[理工] 資結 treegary19941208 [理工] 演算法 KMPhopward Re: [理工] 微分證明Honor1984 [理工] 微分證明chunlin01 [理工] 計組 pipeline之控制信號線與單時脈差別newpuma [理工]105成大資工整數分割hasuekee29 [理工] 離散生成函數newpuma [理工] [線代]1to1相關證明題lemontea1011 [線代］線性映射解特徵TIANPJ [理工] 計組 beq與bne的rs rtnewpuma