天才基本法涉及的概率数学知识 天才基本法中的P

电视剧《天才基本法》第一集，林爸爸在墙壁上写下如图的两个等式：

P=NP？

　　林爸爸对林朝夕说，上面是现在你正在学的问题，下面是我研究的难题，当你看懂下面式子的含义，你就超过我了。上面的勾股定理大家都认识，下面的等式P=NP是什么公式呢？

　　这个等式其实是高额悬赏的七个千禧年难题之一，也是计算机科学领域的最大难题。其中P表示：多项式时间（Polynomial）,NP那就是非多项式时间（NOT Polynomial）。多项式时间不好理解，可多项式咱都懂啊。

多项式

　　在牛顿或者泰勒之前，圆周率的计算是一项高深的工作。我国南北朝时期的数学家祖冲之将圆周率精确地计算到小数点后6位，领先欧洲一千多年。

　　而现在的小学生学会用多项式展开式计算圆周率的方法，一天时间就能轻轻松松超过祖冲之的成就。

圆周率多项式展开式

　　是不是小学生算一天的精度就能远远超过6位！

　　如果之前的割圆术等计算圆周率的方法称之为NP方法，则这种多项式的计算方式就是P方法。而计算机是最擅长处理这类P方法，只要给足够的算力和时间。

P=NP？这是个问题

林爸爸所研究的“P=NP？”称为“P/PN问题“，并不是一个等式，意思就是一个NP问题能不能转化为P问题，即能不能用一个多项式来表示计算机解决这个问题需要的算力或时间，相当于中学数学中的”化是思想“。

一个典型的NP问题就是大整数的因数分解，是密码学中的重要问题，现在还时不时有新闻说发现最大的质数，2021年11月26日发现的最大的质数是2^74207281-1，说明此问题还没能成功地转化为P类问题，不能预测用超级计算机发一现下一个质数所需要的算力与时间。目前这一类NP问题（又称NPC问题）积累起来有3000多个。数学家已经证明了，只要一个NPC问题存在多项式时间的算法，则所有的NPC都可以在多项式时间内解决，那也就太不可思议了，但也不是没有这个可能。如果真的一个NPC问题找到多项式时间的解法，则像密码学此类的问题将迎刃而解，这将对计算机安全构成巨大威胁，其中的利害关系将是非同寻常的。

难怪林朝夕讽刺爸爸是“民科”。