P vs. NP

P vs. NP 其实是提出了这么一个问题:一个可以快速验证真伪的问题是否可以快速的求解?

P 问题指的的是可以快速求解的问题,NP问题是那些不容易求解的问题。但是NP问题有个特性,即如果你一旦找到一个解,这个解的真伪很容易验证.

P vs. NP问题的实质就是NP问题的‘不易求解’仅仅是因为我们还没有找到方法.还是有内在的复杂性.

具体说, 来个乘法:

7 * 13 = ?

如果你没算错的话,7×13=91,2年级那会你应该就会了,那下面这个呢?

? * ? = 91

是不是没那么简单了? 难度再加一点(100 位 十进制数),麻烦分解一下:

15226050279225333605356183781326374297180681149613
80688657908494580122963258952897654000350692006139

= ? * ?

如果你能算出来,而且结果下面一样的话:

15226050279225333605356183781326374297180681149613
80688657908494580122963258952897654000350692006139

=

37975227936943673922808872755445627854565536638199
× 
40094690950920881030683735292761468389214899724061

恭喜你,你刚刚拿到了1000美元, 前提是你穿越到1991年以前,不过你也不要灰心,奖金额十万二十万美金的还有不少,瞅瞅悬赏榜单:

RSA整数分解悬赏

看看下面这个:

124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099

= 

?* ?

这个232位的整数分解奖金5万(美元),更妙的是这个还没有被抢答。最高2048位(二进制)617(十进制)的整数分解奖金高达20万美元,你是不是看到一套发财的金光大道?且慢,RSA不是作加密算法的公司吗,这里面一定有套路…

整数分解是个典型的NP问题,是现在密码学的基石,要不然怎么会这么难 (回忆一下去年丁凡的rsa培训…).

  • 可以挨个拿质数序列 2 3 5 7 11 …去除(查找)
  • 有啥其他更好的方法吗?

再看一下其他的NP问题

分图问题(Maximum Clique Problem)

来自于图算法,在一个图(graph)中找到一个最大的全联接(clique).

具体来说,你的朋友圈是一张图,如果我们尝试在你的朋友圈中,找到一个最大的所有的人都互相之间是朋友的子图。

找到一个最大clique,有上百个节点的图中需要几个世纪的计算机时间, 因为要找到最大的clique,必须查找所有可能组合。

这是一整类问题

  • 整数分解、质数判断(primer factorizations)
  • 分图问题 (Maximum Clique Problem)
  • 调度问题 (Scheduling Problem)
  • 地图着色 (Map Coloring Problem)
  • 蛋白质折叠 (Protein Folding)
  • 装箱问题 (Packing Problem)
  • 担货郎问题 (Travelling salesman problem)

P vs. NP 的数学定义

  • P 代表”polynomial time”
    • 可以快速解决的问题,多项式复杂度
  • NP “nondeterministic polynomial time”
    • 指数复杂度
    • 可以快速验证
    • 可以通过查找来暴力解决, 可以要遍历所有可能的项目实在太耗时了

P = NP or P != NP

所有的这些都是‘大海捞针’问题,遍历所有的可能性,才可能找到答案.

关键在于:是否需要去遍历这些所有的可能性,是否有‘捷径’?找到草垛里的一根针,传统的方式是遍历草垛里的每一根草,聪明的做法是用磁铁‘一下子’找出来,如果磁铁不存在,找针这个行为就是NP的,如果磁铁存在,则NP=P. 对于质数查找来说,有个质数的验证公式

一种验证质数的方式

对于所有的质数p,和a < p, 有:

a^{p-1}\mod p = 1

举例说:对于质数7

p = 7 , a = 2:  (pow 2 6)= 64, mod 7 得到 1, 所以7是质数

对于非质数15

p = 15, a = 2: (pow 2 14) = 16384, mod 15 得到 4,所以15不是质数

所以说,验证质数是可以高度简化的

NP完备(NP-Completeness)

NP完备是解决所有NP问题的钥匙,大意是每个NP问题都可以归结到这个NP问题上。

其实这是一个非常美妙的故事,每个NP问题都有内在的联系,在表象之下,他们本质上是一个问题,如果我们解决了其中一个,就解决了所有。所以只要能解决一个NP问题,NP就不存在了。

如果 P = NP,现代密码学会崩溃;如果P \neq NP ,历史依然沿现在轨道运行.

分图问题很特殊,几乎所有的NP问题都可以转化分图问题,比如整数分解问题可以映射为分图问题。

graph LR
A[Factoring problem] --> B[transformer] 
B --> C[Clique problem]

NP-Hard问题

行文至此,还需指出一点:NP问题只是一类有共性的问题,并不是所有难以求解的问题都是NP问题。理论上所有的围棋策略都是一个决策树的分支,我们应该能够找到一个最优策略, 但我们无法快速的验证我们的最优策略确实是最优的。所以这个问题不是NP问题,而是个NP-Hard问题。

证明P \neq NP?

个人倾向于P不等于NP,但是数学上暂时没有得到证明。

关于P vs. NP的争议:

  • 理论和事实的差距
    • 1.0000001^nn^{1000}
  • P和NP的非此即彼的区分是否明智?
    • 如果有个问题求解的复杂度是n^{log^cn}, 怎么界定它?
  • NP问题是不是现有的离散式计算机体系自身的问题,比如说:量子计算机、模拟计算机体系,可能在这些体系中,NP问题不存在.

参考资料

2016年的p vs. np 问题总结

发表评论

电子邮件地址不会被公开。 必填项已用*标注