NP的NP完全
答案:1 悬赏:10
解决时间 2021-01-19 09:53
- 提问者网友:遮云壑
- 2021-01-19 03:49
NP的NP完全
最佳答案
- 二级知识专家网友:逐風
- 2021-01-19 03:59
要解决P = NP问题,NP完全的概念非常有用。不严格的讲,NP完全问题是NP类中“最难”的问题,也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如,旅行商问题的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。所以若旅行商问题被证明为在P内,则P = NP!旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内,则可以推出P = NP。不幸的是,很多重要的问题被证明为NP完全,但没有一个有已知快速的算法。
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯