P=NP or not
我在研究生时,一次一位教授发起了PvsNP问题的讨论,无意中找到了这本书。
这本书是这个问题的科普版,好比霍金的时间简史,对于这个问题,我可以做一个简单介绍:
计算机学中的PvsNP问题好比物理学中的量子力学,甚至更为重要,解决了这个问题就获得了宇宙的最终真理。那时,即便你是一个平凡人,但是根据一个从中而来的规律一步步来做,你也可以称为巴菲特,爱因斯坦,梵高,莫扎特…… 那是一个任何问题都能够轻易找到最优的解决办法的世界。
P 是指一类能够设计有效解决算法的问题,这里的有效是说算法负责度为线型O(n),就是说你设计的算法不会已经为输入太大以至于几乎无限循环。
NP是指一类现在找不到有效解决算法,但是可以设计有效算法验证的问题,比如寻找路径的问题,我们很难找到最佳的路径,但是如果给出一条路径却可以很快验证。现实中很多问题都是NP问题,物流公司的路线规划,大脑学习的分析,股票的模式,天气的变化,宇宙的演变……
而P=NP 是说这些NP问题都可以归为P问题,也就是说哪些我们找不到有效算法的问题都可以找到有效算法。
比如对于物流公司,如何找到成本最小的规划是一个NP问题,如果P=NP,那么就意味着输入现有的所有用户和货物状态,就可以立即得到最佳的规划,创造最大的价值。
甚至,这个问题的解决也就意味着所有问题的解决,因为我们可以设计算法解决其他的问题。
但是问题在于,大部分的人相信P不等于NP。
这本书是这个问题的科普版,好比霍金的时间简史,对于这个问题,我可以做一个简单介绍:
计算机学中的PvsNP问题好比物理学中的量子力学,甚至更为重要,解决了这个问题就获得了宇宙的最终真理。那时,即便你是一个平凡人,但是根据一个从中而来的规律一步步来做,你也可以称为巴菲特,爱因斯坦,梵高,莫扎特…… 那是一个任何问题都能够轻易找到最优的解决办法的世界。
P 是指一类能够设计有效解决算法的问题,这里的有效是说算法负责度为线型O(n),就是说你设计的算法不会已经为输入太大以至于几乎无限循环。
NP是指一类现在找不到有效解决算法,但是可以设计有效算法验证的问题,比如寻找路径的问题,我们很难找到最佳的路径,但是如果给出一条路径却可以很快验证。现实中很多问题都是NP问题,物流公司的路线规划,大脑学习的分析,股票的模式,天气的变化,宇宙的演变……
而P=NP 是说这些NP问题都可以归为P问题,也就是说哪些我们找不到有效算法的问题都可以找到有效算法。
比如对于物流公司,如何找到成本最小的规划是一个NP问题,如果P=NP,那么就意味着输入现有的所有用户和货物状态,就可以立即得到最佳的规划,创造最大的价值。
甚至,这个问题的解决也就意味着所有问题的解决,因为我们可以设计算法解决其他的问题。
但是问题在于,大部分的人相信P不等于NP。
有关键情节透露