这个看似简单的一个问题，实际上是理论计算机领域最大的未解难题。
2000年，在参考了一个世纪前希尔伯特提出的23个问题的做法之后，克雷数学研究所发布了七道千禧年大奖难题，总价值七百万美金。解答出任何一道问题的第一个人将被授予一百万美金的奖励。其中一道难题正是关于解决P和NP的复杂度问题。这个问题成为了整个计算机领域的焦点，因为这个问题的结论会直接给计算机领域带来截然不同的理论极限和发展前景。
虽然从表面上看，P是否等于NP这个问题非常直接，但它的证明却已困扰了研究人员长达数十年之久。简单地说，P与NP问题问的是，能够被容易解决的问题集合是否也属于能够被容易验证的问题集合中。
让我们来试想一个场景，假设你接收到了一项任务，内容是将一个打碎的茶杯重新粘合在一起。要想检验你是否成功地完成了这项任务是非常简单的——如果成功了，你的面前就会有一个完整的茶杯。但是，将每一块散落的碎片重新粘合起来是件很困难的事。这就是NP问题的一个例子：难解，却容易验证。
假如现在你的任务不是重新粘合破碎的茶杯，而是计算茶杯被打碎成了多少块。这就变成了一个P类问题。相比而言，计算碎片的数量比计算它们之间的联系要容易得多。
为什么叫做P与NP？
当委派给计算机一项任务时，计算机算法需要一定的时间来解决它。那么，如何理解一个算法解决问题需要花费的时间呢？举个例子，假设你有一个未经排序的数字列表，你想写一个算法来找出其中最大的数。这个算法必须查看列表中的所有数字，这是无法避免的。但是，如果它只是记录到目前为止看到的最大数字，那么每个数字只需被查看一次。因此，算法的执行时间与它处理的单元数量成正比——计算机科学家称其为N。
由于有些算法的效率会比其他的算法效率更高或更低，所以它们完成的时间可能与N、N²、N³……有关。其中的关键在于指数是一个常量——1、2、3等等。在这种情况下，算法被称为在是多项式时间内完成的，或简称为P。如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P类问题。（需要说明的是，一个对P类问题的常见误解是以为它们都是能很快解决的问题，但其实，P类问题有可能是天荒地老都无法解出的问题。）
但可惜的是，并不是所有的问题都这样。一些问题的解决需要花费的时间正比于2ᴺ、3ᴺ……在这种情况下，N是指数，这意味着算法要处理的每个单元的复杂度都呈指数级增长。在这种情况下，算法可以在指数时间内完成，或简称为NP（它实际上意为不确定性多项式时间）。
这二者之间可以有非常巨大的差别。举个例子，假如一个有100个单元的P算法，它完成工作的时间长度正比于N³，解决问题所需的时间大约是3小时；但如果它是一个NP算法，完成任务的时间与2ᴺ成正比，那么它花费的时间可以达到约3亿亿年。
重要之处
问题“P是否等于NP”的另一种问法是，每一个困难问题是否都包含一个简单但隐藏的解。这两种类型的问题是否不可避免地彼此分离？是否一些问题的本质就是复杂的？
如果P确实等于NP，那么它对我们的生活将产生重大影响。一个主要的好处是，许多NP问题被称为NP完全问题，这意味着它们的解可以迅速适用于任何其他NP完全问题。因此，找到一种快速解决一个NP完全问题的方法，将在解决所有其他NP完全问题方面取得重大进展。
有哪些例子是NP问题呢？有一个主要问题是许多研究人员的关注焦点。现代密码学主要依赖于难以破解但易于被检查的代码，比如你的帐户密码：检查它们是否正确是很简单的，但是要靠蛮力硬猜每一个字母和数字的排列就要花费很长很长的时间。在网上订购商品时保护信用卡号码背后的加密技术也是NP加密技术的一个例子。如果P = NP，那么可能几乎所有加密的破解都会突然变得非常容易。
虽然如果P = NP成立的话，我们将失去表面上的互联网安全，造成损失惨重的后果，但它也将产生许多有益的后果。计算机科学家Lance Fortnow在一篇文章中归纳总结了一部分重要的结果：
各种形式的运输方式的调度将被优化，从而能提供更快、更便宜的物流与交通。制造商可以提高生产力，减少浪费。我在这里所说的还只触及了一些表面问题。通过奥卡姆剃刀原理，学习将变得很容易——我们只需找到与数据一致的最小程序。近乎完美的视觉识别、语言理解和翻译等一切学习任务都变得显而易见。我们还能更好地预测天气、地震和其他自然现象。
P是否等于NP是非常基本的问题，能因其而得到巨大改善的任务数不甚数。例如，从蛋白质的氨基酸序列来预测蛋白质的结构将变得非常容易，这对药物设计和生物技术来说是一个重要里程碑。另一个常被提到的NP问题是，如何确定计算机芯片上最有效的晶体管布局，从而能显著提高计算能力。
事实上，证明P = NP会使几乎对所有其他数学问题的求解都变得更加容易。如果P = NP最终得到证明，将会彻底颠覆当前社会的技术和经济基础。这个问题的解决很有可能成为一个比互联网的发明意义更重大的创新推动。
科学共识
不过，大多数计算机科学家并不相信P=NP。根据2001年的一项调查显示，有61%的人相信P≠NP；而2012年的调查则显示，相信P≠NP的人达到了83%。要真的证明P ≠ NP是非常困难的，但是所有证明P = NP的尝试都失败了，这表明这两类问题是互不相容的。麻省理工学院的科学家Scott Aronson写过一篇博文，列出了P ≠ NP的10个原因，其中第9条提出了这样一个论据，既有力地反驳了P = NP的观点，又简洁地描述了假如P = NP成立的结果：
如果P=NP，那么世界将与我们通常所认为的完全不同。“创造性的飞跃”将没有特殊价值；一旦找到问题的解，那么在解决问题与认可解决方案之间没有根本间隔。任何能欣赏交响乐的人都是莫扎特，每个能一步一步论证的人都是高斯，每个能认识到好的投资策略的人都是巴菲特。
参考来源：
https://bigthink.com/technology-innovation/what-is-p-vs-np?rebelltitem=5#rebelltitem5
http://news.mit.edu/2009/explainer-pnp
https://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext
https://www.scottaaronson.com/blog/?p=122
http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf
发表于 2019-1-6 17:19
收藏
分享