可能与不可能的边界 P/NP问题趣史

第一章 金券

  假如我们想在数以万计的巧克力中找到一张含有金券的巧克力需要怎么做?(一共有5张金券)

  有大量的时间，请大量的人，大量的金钱(买下非常非常多的巧克力)，然后人工筛选

 

  Mary的公司定制了一个计划，需要从她的家乡出发，然后经过48个州，并像这些州推销木锥,为了

节省开支，需要定制一个路线，即启动为Mary的家乡,然后经过48个州，距离最短。其实这个计算相

 

当于 48! 这么大的计算复杂度。大概是1.2 * 10^61，这个数有62位，以目前最快的计算机计算也需

 

要几亿亿年时间。这个就是著名的 旅行推销员问题

 

  划分难题,假设有个数有100位,每个位之和相加为2000，能将其平分为两组，每组50位，总和为

 

1000吗? 这个也是NP问题，即使能暴力计算，但如果是1W位长度，100W位长度能计算出来吗?

 

  GPS定位，假设我们从A地去往B，中间有非常非常多的路线可以选择，GPS导航是无法在这么短的时

 

间内计算完成的。类似旅行推销员问题，而这个问题有一个很有意思的性质，即从A到B要经过C，那

 

么计算A->C->B 的最短路线一定是 A到C的最短路线 + C到B的最短路径

A到B的最短路线只可能比AC+CB的路线更短

所以GPC导航使就使用了这种性质，可以快速的缩小计算范围

 

  人类的手能完成各种事情，但是通过机械模拟就非常困难，因为即使要完成一些简单的工作也需要

 

大量的代码，如果P=NP，那么就所有的事情最终都可以自动化完成了

  量子计算不可能完全解决N/NP问题，但是可以解决很多目前计算机束手无策的问题

 

  克雷数学研究所在2000年列出了7个千禧年的难题:(庞加莱猜想已被解决)

1.贝赫和斯维衲通-戴尔猜想

2.霍奇猜想

3.纳维-斯托克斯方程

4.P/NP问题

5.庞加莱猜想

6.黎曼猜想

7.杨-米尔斯理论

 

 

 

 

 

第二章 美妙的世界

如果P=NP，那么世界将是怎样的?

某一年一位数学家证明了 P=NP，不过算法实行时间过长，缺乏实际价值

后来另一位科学家对算法进行了改良，大幅度的提升了效率，但还是不够

又过了一段时间一些科学家继续优化代码，并实际解决了一些常见的NP问题

一位博士利用之前所有的资源继续优化，而且写了一个程序，让计算机自己找出最优的算法

最终这个算法被命名 厄巴纳算法，因为算法的重要性，最终算法被公开

 

也许癌症可以轻松的解决

首先鉴别出某个正常人的DNA和癌细胞的突变DNA，然后制造特定的蛋白，其折叠方式可以饿死

癌细胞，而且对正常细胞没有任何影响。最终吃两星期药就好了，当然这是根据某个人的DNA特指

的，所以对其他人不起作用，甚至会有严重后果。

 

体育比赛也会发现惊人的变化

以前比赛的场次都是随机安排的，因为比赛是在室外，如果碰到不好的天气也没办法。但现在可以

精准的预测天气，所有的比赛都是在最好的天气举行的

计算机预测比赛结果准确率非常之高

进入体育场不用门票了，脸部识别系统配合后台购票记录可以精准识别观众是否买票了

算法可以非常好的模拟场上任意角度，而且非常逼真

连转播员都可以大幅度减少，通过算法可以精准的将英语翻译为其他国家语言

一些小型中型比赛甚至都不用裁判而用计算机了

 

奥卡姆剃刀

即主张最简单的解释通常是最好的解释，剃刀一词比喻把一个理论中纠缠复杂的部分像胡子一样剔除

笛卡尔《方法论》中的 我思故我在

开普勒观察行星运动，归纳出一系列运动路线和速度定律，但是无法解释他

牛顿将奥卡姆剃刀运用到物理世界，发明了著名的运动定律:

1.如果不给物理施加任何力，静止的物体会保持静止，运动的物体速度保持不变

2.施加于物体上的力将产生一个风与其大小成正比的固定加速度

3.一个物体给另一个物体施加力，则施力物理也会受到来自受力物体的大小相等方向相反的力

爱因斯坦则发现速度接近光速的物体，牛顿的定律不成立，爱因斯坦的名言:

  把所有的事情变得尽可能简单，而不可过于简单

而对于非常小的粒子，爱因斯坦的理论也不成立了，它们所服从的法则被称为量子力学

科学家们试图能找到一种能融合广义相对论和量子力学的理论，即所谓的 大统一理论

   简单的模型永远无法反映世界的全部复杂性，但它们通常可以很接近这个目标

 

机器学习就是用大量的数据训练一个算法，比如识别手写的支票，人脸识别，图书推荐等

如果P=NP，我们只需要将大量的数据交给算法，然后它完成剩下的工作，此时我们几乎能了解

所有的事务

 

厄巴纳算法甚至对艺术也可以产生影响

总统候选的讲稿，都是可以根据之前的海量数据，然后由算法生成一个完美的讲稿

可以完成大师们未完成的名作:

普契尼的歌剧《图兰朵》，马勒的《第十交响曲》，舒伯特的《第八交响曲》

也能由算法自动创造一个交响曲，能将已故歌星的嗓音模仿的惟妙惟肖

出现一种自动生成的，完全符合你口味的小说

游戏里的故事情节不再是线性了，而是完全由玩家意识支配

厄巴纳算法可以根据DNA预测出犯罪嫌疑人的身高体重血型眼睛肤色等，从而根据这些信息自动素描

出犯罪人的相貌和年龄

 

由于解决了P=NP，公钥加密失效了，只能使用一次性秘钥

到处都安放了摄像头，计算机可以精准识别人的兴趣爱好，可以精确的推荐

任何恐怖分子都可以轻松识别

从秘书到中层管理，各种行业的人都受到算法的威胁，可能失业

大学里开始新课程，教受如何最快速的运用算法解决问题

 

只要能辨识，就能找到，前提是P=NP，所以大部分科学家认为P<>NP

以上的故事当中有一部分可能会变成现实

 

 

 

 

 

第八章 秘密

最早的加密方式为:凯撒加密，即将A->B, B->C 这样的方式:

hello -> ifmmp

 

15世纪文艺复兴时期，阿尔伯蒂创造了一种更复杂的加密方式: 多字母加密法

即对消息的不同部分使用不同的替换规则

 

艾伦坡的小说《金甲虫》属于第一批描述密码的小说

柯南道尔的小说《跳舞的小人》也有描述破译密码的情节

 

随着机械时代出现了一批加密解密的机器设备，谢尔比乌斯发明了恩尼格玛密码机

相当于阿尔伯蒂多字母加密法的更复杂版本

二战中德军就使用了这种加密机器，最终被图灵破译

 

加密和解密一直以来都是一场猫鼠游戏，但是1976年斯坦福的迪菲和赫尔曼彻底改变了这个格局

使用NP问题来隐藏自己的秘密，从此以后加密后的结果再也无法直接破译

使用恩尼格玛密码机和古典加密时，双方都必须约定好一套加密规则，也就是对称加密

但是互联网本身是不安全的，对称加密也不安全

迪菲和赫尔曼提出了 公钥加密

罗纳德，阿迪沙米尔，伦纳德阿德曼 联合发明了 RSA算法

RSA算法的核心是因数分解难题，也就是NP问题

 

如果P=NP那么所有公钥加密算法都将失效，只有一种方式可行，就是一次性密码本

假设消息为12个字符:

FIDDLESTICKS

密码本是一个随机数，并且和消息一样长:

JXORMQNAMRHC

无论是否P=NP，都无法通过密码本对消息本身有任何了解

但是这样的缺点也很明显，密码本只能使用一次，而且如何安全的在双方之间共享也是难题

在P=NP的世界中，也许我们会使用一个封装好的U盘，里面装满了一次性的密码本

 

现实世界中可以使用猜硬币来决定 是或否，如果是用电话沟通呢?

A 随即产生一个数字，经过公钥加密，之后将 公钥 和加密后的数 发给B

B 猜测结果，并用公钥加密后，将信息发送给A

A 用私钥解密就可以知道答案了，为保证公平性，A将私钥发送B

B 用私钥解密最开始A发来的加密信息，就知道原始的随即数字了，这样A B都知道原始结果了

甚至可以使用这种方法来玩 国际象棋，强手棋，但是玩纸牌就复杂很多了

 

如果使用了云提供商的存储服务，但是又不信任它，简单的使用公钥加密还不行

此时需要完全同态的加密方法，这种方法可以从加密的输入直接得到加密的输出

 

密码学和随机数有直接的关系，但是计算机生成的只是 伪随机数

伪随机数只有问题复杂到一定程度才有效，而P=NP的话，那么抛硬币这种随即事件将不再是靠运气了

 

现代密码学构建在NP完全问题的困难性以及P<>NP的假设之上的，也是该学科目前的心腹之患

人们也许会发明理论上牢不可破的加密方法，但是基本上永远都不可能实现绝对不会泄密的保密系统

 

 

 

 

 

第九章 量子

量子计算可以比普通的计算机更快的解决某些问题

 

假设A和B都是球迷，有一场比赛热火VS尼克斯，在昨天已经结束了，但是A和B都没看

A和B刻意不听任何比赛结果的报道，然后在网上看了比赛的录播视频

比赛最后一刻最后一投，此时真正的比赛早就结束了，但是A和B如果不看最后一秒，谁也不知道比赛

的结果，结果是随机的，但可以肯定是不是热火赢就是尼克斯赢，而且两人看到的结果一样。

这个故事和量子计算的关系:

  传统的计算机最基本的元素是 比特(bit)，它只能取两个值中的一个

  量子计算机的基本元素叫: 量子比特(quantum bit)，量子比特的取值能介于两个值之间

 

一个量子比特可以在一个二维的圆圈上取值，也是随机的

两个量子比特则需要四维的版本来表示，30个量子，则超过1万亿个纬度，这种纬度是呈指数增长的

可以使用这种方式来解决NP问题

3*10^150操作，有科学家证明至少需要2*10^75操作，所以即便造出了量子计算机也无法解决NP问题

贝尔实验室的肖尔发现量子计算可以轻松解决质因数分解

但是对通用的NP问题无效

 

经典加密和量子加密结合，理论上可以创造出 不可破译的密码

因为量子是不可观察的，就是海森堡的测不准原则，薛定谔猫佯谬

国际密码学会对应用于公开钥密码系统的加密算法推荐了两种：

1.基于大整数因子分解难题的RSA算法

2.基于椭圆曲线上离散对数计算难题的ECC算法

 

 

量子传输

可以将物体原地分解，然后在另一个地方毛发无损的重现它

但是首先双方都需要准备一些彼此缠绕的量子比特

即A和B拥有相同的纠缠量子

A再准备一些物体的描述信息量子，然后观察这些量子，将这些量子发给B

B根据这些描述信息，重新组装事先准备好的量子，这样就完成了物体的量子传输

 

 

 

 

 

 第十章 未来

摩尔定律，并行计算，未来几十年可能会出现百万核或者几十亿核的计算机

P/NP问题在并行计算的世界里仍然是有效的

Nick's Class，对于那些能用并行算法快速解决的问题叫做NC

我们不知道是否P=NC，更不知道是否有NP=NC

NP=NC意味着一个NP搜索问题能用极快的速度在并行计算机上有效的解决，NP=NC的可能性极小

 

facebook，谷歌，欧洲大型强粒子对撞机每天产生海量的数据

虽然这些数据量很大，但是其中大部分是无用信息，如果P=NP我们只要用算法把数据过一遍，挑出

重要的部分，再用奥卡姆剃刀法则工具，就能形成对数据的理解和预测能力

通过拥有更多的数据胜过拥有更好的算法，谷歌在垃圾邮件检查，语音识别做的不错，得益于它有

海量的数据

 

如果一切事物网络话，不用笔做记录，你的衣服告诉你如何搭配更好

不会再丢失钱包，通过手机远程开门，自动驾驶汽车

当然这些问题也涉及了一些P/NP问题

 

P/NP问题需要过20，200，甚至2000年才能证明

当面临一个NP问题时，不可能找到一个在所有情况下都能解决该问题的算法。这时就需要借助其他

工具，如近似计算，启发式方法，暴力破解等方法的组合

P/NP问题让各个学术界团结在一起，物理学家的实验结果可能对经济学家有帮助或启发

P/NP问题归根结底与自然本身的极限有关，与生物和物理系统进化的极限有关，甚至可以说与人类

思想所能达到的极限有关。