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