无法立即解决的No.100P与NP问题

2023-11-22 理论教育版权反馈

【摘要】：然而，有些问题只能用执行起来效率较以上逊色许多的算法来解决——它们属于NP问题。NP问题往往具有重要的现实意义，它们推动我们去找寻能将其解决的更优算法。也就是说，这个NP问题会不会其实是P问题？有些问题被归为NP问题，是否是因为我们目前还没能找到将其解决的更优算法，或者我们根本无法找到这样的算法？

假设一个销售员计划走访几座城市，请问走哪一条路线最高效？这个问题被视为NP问题。

1.多维度看全

计算复杂性理论研究的是一个算法（可以通过机器执行的一组程序）执行起来的难度。它尤其会参考随着输入数据的增加该算法所用时间的变化情况。

假设你要在10个人里找到年纪最大的，你只需要挨个把每个人的年龄问清楚，并且每问完一个人，都记下谁是目前为止年纪最大的。这样，10步之后，你就会知道谁是这群人中年纪最大的了。如果总人数变为100，就需要100步。

我们一般将这种问题称为可在线性时间内解决的问题。许多问题虽然无法在线性时间内被解决，但可以在某个有关输入数据指标多少的多项式时间内被解决。上述问题都属于P（Polynomial-time）问题。

然而，有些问题只能用执行起来效率较以上逊色许多的算法来解决——它们属于NP（non-polynomial）问题。

2.关键点梳理

由于包含大量数据，NP问题是十足的噩梦。将其解决可能需要花费几个小时，甚至数天。NP问题往往具有重要的现实意义，它们推动我们去找寻能将其解决的更优算法。

然而，我们是否能找到更优算法呢？一个问题被归为NP问题，是否只是因为我们还没能找到“正确”的解决方法呢？也就是说，这个NP问题会不会其实是P问题？或者是否有些问题由于本身过于复杂，以至于不能在多项式时间内被解决？至少在写作本书之际，我们还不清楚答案是什么。(www.chuimin.cn)

参考阅读//

No. 23 多项式，第50页

No. 92 阶乘，第188页