1701006342
在2002年，对于100位研究者的调查，61人相信答案是否定的，9个人相信答案是肯定的，22个人不确定，而8个相信该问题可能所接受的公理独立，所以不可能证明或证否。所以P/NP问题也是Clay研究所的七个百万美元大奖问题之一。
1701006343
1701006344
“NP完全”问题（或者叫NPC）的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的。科学家现在相信P、NP和NPC类之间的关系如图4-17所示，其中P和NPC类不交。
1701006345
1701006346
1701006347
1701006348
1701006349
图4-17 P、NP和NPC类之间的关系图
1701006350
1701006351
1701006352
假设的复杂度类的图解，如N＝NP则三个类相同，本质上，P＝NP问题如：如果“是/不是”问题的正面答案可以很快验证，其答案也可以很快计算。
1701006353
1701006354
例如，给定一个大数Y，我们可以问Y是否是复合数。例如，我们可能问53308290611是否有非平凡的因子，回答是肯定的，虽然手工找出一个因子很麻烦。从另一个方面讲，如果有人声称答案是“对”，因为224737可以整除53308290611，则我们可以很快用一个除法来验证。
1701006355
1701006356
用于验证一个正面答案所需的信息也称为证书。所以我们的结论是，给定正确的证书，问题的正面答案可以很快的（在多项式时间内）验证，这就属于一个NP问题。
1701006357
1701006358
要解决P＝NP问题，“NP完全”的概念非常有用。不严格的讲，“NP完全”问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。
1701006359
1701006360
例如，旅行商问题的判定问题版本是“NP完全”的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题。所以若旅行商问题被证明为在P内，则P＝NP，旅行商问题是很多这样的NP完全的问题之一。若任何一个“NP完全”的问题在P内，则可以推出P＝NP。不幸的是，很多重要的问题被证明为“NP完全”，但没有一个有已知快速的算法。
1701006361
1701006362
【问题】那么，P真的容易处理吗？
1701006363
1701006364
【分析】
1701006365
1701006366
上面所有的讨论，假设“在P中”表示“容易”，而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点。
1701006367
1701006368
（1）它忽略了常数因子。一个需要10100n时间的问题是属于P的（它是线性时间的），但是事实上完全无法处理。一个需要102000n时间的问题不是在P中的（它是指数时间的），但是对于NP取值直到几千时还是很容易处理的。
1701006369
1701006370
1701006371
（2）它忽略了指数的大小。一个时间复杂度1000n属于P，但是很难对付。已经证明在P中存在需要任意大的指数的问题。一个时间复杂度的问题不属于P，但对于n取值直到几千还是容易应对的。
1701006372
1701006373
（3）它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间n中解决，但是偶尔，你会看到需要时间2n才能解决的特例。这个问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于P。
1701006374
1701006375
（4）它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于P，虽然事实上它可以很快求解。这实际上是解决属于NP而还不知道是否属于P的问题的一个办法。
1701006376
1701006377
如“量子电脑”计算模型，可能可以快速的解决一些尚未知道是否属于P的问题；但是，没有一个能够解决的问题是“NP完全”的。不过，必须注意到P和NP问题的定义是采用像图灵机这样的经典计算模型来表述的。所以，即使一个量子计算机算法被发现能够有效的解决一个“NP完全”问题，我们也只是有了一个快速解决困难问题的实际方法，而不是数学类P和NP相等的证明。
1701006378
1701006379
1701006380
多数计算机科学家相信。经过数十年的研究，没有人能够发现一个“NP完全”问题的多项式时间算法。而且，人们早在“NP完全”的概念出现前就开始寻求这些算法了。进一步地，P＝NP这样的结果会导出很多惊人的结果，那些结果现在被相信是不成立的，例如NP＝NP和P＝PH。
1701006381
1701006382
也有这样论证的：问题较难求解（NP）但容易验证（P），这和我们日常经验是相符的。
1701006383
1701006384
1701006385
从另一方面讲，某些研究者认为我们过于相信，而应该也去寻找P＝NP的证明。
1701006386
1701006387
我们只是在开始探索的起点，只要你用于挑战，成功就在前方。
1701006388
1701006389
1701006390
1701006391