NP猜想（一） (4-1)

P＝NP？

P、NP、NPC、NP、hard

1900年，德国大数学家大卫·希尔伯特在巴黎提出了23个待解决的数学问题，这些问题直接影响、指导了一百多年的数学研究方向。为了呼应一个世纪前希尔伯特在世纪之初通过提问题而指导研究方向的传统，2000年5月24日美国克雷数学研究所( Clay Mathematics Institute , CMI ) 公布了七个有待证明或证伪的数学猜想，并为每个猜想给出了100万美金的奖金。

科学发展越来越深入，学科专业划分越来越细致，可能如今已经没有像当年的希尔伯特那样的集大成的数学家了，所以这七个问题是由证明了费马大定理的英国数学家安德鲁·怀尔斯、菲尔兹奖和阿贝尔奖双奖获得者英国数学家阿蒂亚（前些日子声称证明了黎曼猜想的那个老人）、美国数学家阿贝尔奖获得者约翰·泰特、法国数学家阿兰·孔涅（ Alain Connes ）、弦论创始人美国数学家物理学家威滕等科学家共同讨论确定的。

这七个问题可以说在当今数学及数学物理领域是赫赫有名，其中的第一个问题就是被称为“NP=P”的问题。这是一个看起来不太像传统数学猜想的问题，其实它属于计算复杂性理论的问题，IT行业的人士可能对这个问题更熟悉一些。今天我们就来聊聊这个问题。

一、“NP=P”到底是个什么问题？

要知道“NP=P”是个什么问题，先要知道什么是“P类问题”，什么是“NP类问题”，而这两个概念又和计算理论中的时间复杂度有关。不过不用担心，这几个概念都不是很复杂。

简单的说，解决一个问题的某种算法所需要的计算量（或计算步骤）随着这个问题的规模增长而增长的速度就被称为这个算法的时间复杂度。要注意的是，时间复杂度本质上指的是计算量增长的速度而不是这个算法运行的时间。例如：

（1）我们要计算前n个自然数的和，如果使用最直接而笨拙的方法，需要计算n-1次加法，那么可以认为这个算法的时间复杂度就是“n-1”，记作O(n-1)或者O(n)。之所以可以记作O(n)，是因为随着n的增大，1这个常数就忽略不计了。

（2）如果我们要把n个不同的自然数排序，那么就需要对这些自然数的大小进行比较。我们也采用最笨拙的算法，也就是将每两个自然数都做一次比较，那么需要比较n(n-1)/2次，时间复杂度可以记为

n² n

O(─ – ─)

2 2

n²

，或者记为O(─) 。

2

（3）下面举一个更复杂些的例子。给出一个含有n个逻辑变量的逻辑表达式，请判断这个表达式是否是一个“重言”的逻辑表达式。“重言”的意思是说这个表达式无论所包含的n个逻辑变量怎么取值，其结果都是真，类似于我们语言中的“废话”（如“明天要么下雨要么不下雨”）。最简单的重言表达式如 A∨ˉA ，其结果永远为真。我们如果也采用最笨拙的算法，穷举出n个逻辑变量的全部可能的组合，计算每种组合下逻辑表达式的值，如果都是真，就说明这个逻辑表达式是重言的。n个逻辑变量全部可能的组合有 2ⁿ 种，每种组合要进行大约P(n)次逻辑运算（P(n)是n的某个多项式），因此其时间复杂度为O(P(n) · 2ⁿ)

当然，对于同样的问题，采用不同的算法其时间复杂度不一定相同。如果某个问题，我们能够找到的最优算法的时间复杂度是n的多项式函数，我们就说这个问题属于“P类问题”。这里面的P就是多项式的英文（Polynomial）的首字母。前面例子中的（1）和（2）就属于“P类问题”。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。