092 雷声滚滚，一扫浊世 (第2/18页)

曾证明费马大定理的安德鲁·怀尔斯，荣获过菲尔兹、阿贝尔双数学奖的阿蒂亚，美国数学家约翰·泰特，甚至还包括了弦理论创始人物理学家威腾等等一众科学家坐在一起讨论新世纪难题。

    就这样传说中的千禧年七大难题诞生了。NP=P?成为了千禧年难题之首，而已经被宁孑证明的NS方程问题，则同样属于一个困扰了数学家许多年的超级难题。

    当然关于NP=P？也有很长一段历史。

    早在1971年计算复杂理论的科学家斯蒂芬·库克就在其《定理证明过程的复杂性》论文中提到了一类极为特殊的问题——NP-C问题。这类问题有两个特点，首先它必须是一个NP问题，其次任何其它NP类问题都可以归约到这个问题。

    显然这种问题是非常复杂的，事实上当时的学术界一直怀疑是否真的有这种问题存在。

    但牛人终究是牛人，在提出了这类问题后，斯蒂芬·库克还真找到了一个问题，并通过图灵机的方式，证明了他提出的这个问题就属于NPC问题，也就是NP完全问题。

    其定义为“给出一个含有n个逻辑变量的逻辑表达式，判断这个表达式是否可能取值为真，也就是判断这个逻辑表达式是否是可被满足的。”因为这个定义，所以该类问题又被称作为“可满足性问题”。

    这里不需要管斯蒂芬·库克开了多大的脑洞，反正他通过这种方式证明了他提出的问题属于NPC问题之后，数学界著名的库克定理就此诞生“可满足性问题是一个NPC”问题。

    当斯蒂芬·库克完成了这个开创性的工作之后，次年得到启发的数学家便一连找出了21个NPC类问题。比如大名鼎鼎的“哈密顿循环”、