八.NP=P？的终极证明 原创：小宇宙科学哲学—卢山

关键词：NP=P？

提 要：20世纪的重大难题千年大奖问题NP=P?的猜想

基本概念：

P类问题是可以在多项式时间内直接得出答案，直接高效求解的问题，算法运行时间是输入规模的多项式级别(o（n∧k）),比如排序、查找、简单计算等。

NP类问题是所有的多项式非确定性问题，答案可以高效验证，但不知道能不能高效直接算出。也就是给你一个解，你可以在多项式时间判断它对不对，但自己从头找解可能非常难和非常慢。非确定性问题一旦难度提升，指数时间o(2∧n)就会爆炸式增长，规模一大就算不动。

引 言：

例如：在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。宴会的主人向你提议说，你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟，你就能向那里扫视，并且发现宴会的主人是正确的。然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每个人，看是否有你认识的人。

生成问题的一个解通常比验证一个给定的解时间花费要多得多，这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数13717421可以写成两个较小的数的乘积，你可能不知道是否应该相信他，但是如果他告诉你，它可以分解为3607乘上3803，那么你就可以用一个袖珍计算器容易验证这是对的。

人们发现，所有的多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，是否这类问题存在一个确定性算法，可以在多项式时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是因为没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂文•考克于1971年陈述的。这说明运用我们现有的数学工具和方法无法解决这一突出问题，必须创建新的数学工具和方法。

本 论：运用恒等定理证明NP≠P。

一.系统分析问题：通过系统分析，NP=P？存在两个方面的证明：第一，NP类问题（包括NP完全问题）是否等同于P类问题？第二，NP类问题是否可以转换为P类问题，从而使NP=P？

第一个方面问题，依据恒等定理，结合P类问题和NP类问题的基本概念，P类问题和NP类问题属于不同概念的两个问题，不具有唯一性，不符合恒等定理，所以不相等。

第二个方面问题，NP类问题是否存在一个确定性算法，可以在多项式时间内，直接算出或是搜寻出正确的答案呢？或者说是否可以转换为P类问题？

典型例子：1.数独：填完整张很难，给你一份填好的盘面，几秒就能检查是否合规；

2. 旅行商判定问题：是否存在一条路线，走遍所有城市总距离＜1000公里，验证路线很简单，寻找路线极难；

从上面举例的宴会识人、整数分解、数独和旅行商判定问题来说，是完全不能转换的。因为NP类问题在没有提示或暗示的情况下，存在多重不确定性因素。例如宴会识人中的女士罗丝，去了还是没有去不确定，去了之后，在宴会厅的具体位置不确定等；整数分解在给出一个任意的大奇数，这个大奇数不能确定，而大奇数发生变化则分解的两个数同时发生变化，致使分解的两个数也不确定；数独里填写的 数字没有确定，横线和竖线所有数相加的总和或者相乘的总积就不能确定；还有就是旅行商判定问题中所走的路线不能确定，总的行程就无法确定等。如果NP类问题能够转换成P类问题，那么NP类问题就完全是P类问题了，还有必要分P类问题和NP类问题吗？这就像一个人的银行卡10多年都没有动过，一旦需要救急或者密码升级更改的时候，这个人记住了以前的密码，就可以输入正确的密码进行验证，并直接进行后续的操作；而忘记了以前的密码，就需要边回忆边试错边验证，直至输入正确的密码验证通过了，才能进行后续的操作。

二.具体论证：用反证法进行证明。

假如NP=P，或者说如果NP类问题与P类问题相等，在恒等的情况下，就表示是相同的唯一性问题。也就是说P类问题是可以在多项式时间直接求出答案的问题，那么NP类问题同样是可以在多项式时间直接求出答案的问题；如果NP是那些验证容易求解很难的问题，要使P=NP，则P类问题同样是那些验证容易求解很难的问题，意思是P=NP表示具有相同的唯一性问题，对于相同的唯一性问题根本就没有P类问题和NP类问题之分。而既然有P类问题与NP类问题之分，也就是说P类问题与NP类问题属于两个不同的问题，则NP≠P。