# 详细信息
P 类问题：所有可以在多项式时间内求解的判定问题构成 P 类问题。判定问题_：_判断是否有一种能够解决某一类问题的能行算法的研究课题。
NP 类问题：所有的非确定性多项式时间可解的判定问题构成 NP 类问题。非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。设算法 A 是解一个判定问题 Q 的非确定性算法，如果 A 的验证阶段能在多项式时间内完成，则称 A 是一个多项式时间非确定性算法。有些计算问题是确定性的，例如加减乘除，只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式能推出下一个质数是多少呢？这种问题的答案，是无法直接计算得到的，只能通过间接的 “猜算” 来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你 “猜算” 的答案正确与否的算法，假如可以在多项式（polynomial）时间内算出来，就叫做多项式非确定性问题。
NPC 问题：NP 中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间的算法，那么所有 NP 问题都是多项式时间可解的。这些问题被称为 NP - 完全问题 (NPC 问题)。
# 举例叙述
在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。你的主人向你提议说，你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟，你就能向那里扫视，并且发现你的主人是正确的。然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认识的人。
生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数 13,717,421 可以写成两个较小的数的乘积，你可能不知道是否应该相信他，但是如果他告诉你他可以因式分解为 3607 乘上 3803，那么你就可以用一个袖珍计算器容易验证这是对的。人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，是否这类问题，存在一个确定性算法，可以在多项式时间内，直接算出或是搜寻出正确的答案呢？这就是著名的 NP=P？的猜想。 不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂文・考克于 1971 年陈述的。
# 千僖难题
# 背景
美国麻州的克雷（Clay）数学研究所于 2000 年 5 月 24 日在巴黎法兰西学院宣布了一件被媒体炒得火热的大事：对七个 “千僖年数学难题” 的每一个悬赏一百万美元。
# 内容
“千僖难题” 之一：P （确定性多项式算法）对 NP （非确定性多项式算法）
“千僖难题” 之二：霍奇（Hodge）猜想
“千僖难题” 之三：庞加莱（Poincare）猜想
“千僖难题” 之四：黎曼（Riemann）假设
“千僖难题” 之五：杨－米尔斯（Yang-Mills）存在性和质量缺口
“千僖难题” 之六：纳维叶－斯托克斯（Navier-Stokes）方程的存在性与光滑性
“千僖难题” 之七：贝赫（Birch）和斯维讷通－戴尔（Swinnerton-Dyer）猜想
# 评价
NP 完全问题排在百万美元大奖的首位，足见他的显赫地位和无穷魅力。
# 简介
NP 就是 Non-deterministic Polynomial 的问题，也即是多项式复杂程度的非确定性问题。而如果任何一个 NP 问题都能通过一个多项式时间算法转换为某个 NP 问题，那么这个 NP 问题就称为 NP 完全问题（Non-deterministic Polynomial complete problem）。NP 完全问题也叫做 NPC 问题。 [1]
有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。
这种问题的答案，是无法直接计算得到的，只能通过间接的 “猜算” 来得到结果。这就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你 “猜算” 的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。 [2]
完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。
人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，是否这类问题存在一个确定性算法，可以在多项式时间内直接算出或是搜寻出正确的答案呢？这就是著名的 NP=P？的猜想。
解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定 NP 完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。
# 搜索方法
# 近邻法
近邻法（nearest neighbor) 推销员从某个城镇出发，永远选择前往最近且尚未去过的城镇，最后再返回原先的出发点。这方法简单，也许是多数人的直觉做法，但是近邻法的短视使其表现非常不好，通常后段的路程会非常痛苦。
# 插入法
插入法（insertion) 先产生连接部分点的子路线，再根据某种法则将其它的点逐一加入路线。比如最近插入法（nearest insertion），先针对外围的点建构子路线，然后从剩余的点里面评估何者加入后路线总长度增加的幅度最小，再将这个点加入路线。又比如最远插入法（farthest insertion），是从剩余的点里面选择距离子路线最远的点，有点先苦后甜的滋味。
# 模拟退火算法
模拟退火算法（Simulated Annealing) 来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据 Metropolis 准则，粒子在温度 T 时趋于平衡的概率为 e-ΔE/(kT），其中 E 为温度 T 时的内能，ΔE 为其改变量，k 为 Boltzmann 常数。用固体退火模拟组合优化问题，将内能 E 模拟为目标函数值 f，温度 T 演化成控制参数 t，即得到解组合优化问题的模拟退火算法：由初始解 i 和控制参数初值 t 开始，对当前解重复 “产生新解→计算目标函数差→接受或舍弃” 的迭代，并逐步衰减 t 值，算法终止时的当前解即为所得近似最优解。
# 遗传算法
遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体的结构上，其染色体包含若干基因，相应的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体之间的交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力是对应着一个染色体的一个数值来衡量；染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。 [3]
# 神经网络算法
根据一个简化的统计，人脑由百亿条神经组成 — 每条神经平均连结到其它几千条神经。通过这种连结方式，神经可以收发不同数量的能量。神经的一个非常重要的功能是它们对能量的接受并不是立即作出响应，而是将它们累加起来，当这个累加的总和达到某个临界阈值时，它们将它们自己的那部分能量发送给其它的神经。大脑通过调节这些连结的数目和强度进行学习。尽管这是个生物行为的简化描述。但同样可以充分有力地被看作是神经网络的模型。
# 填字游戏
填字游戏是一种最常见的益智纸上游戏，也是 NP 完全问题之一，游戏一般给出一个矩形的表格。这个表格被分割为若干个大小相同的方格，方格的颜色有白色与黑色两种。白色的方格组成一些交叉的行与列，行列的长度不等。玩家根据题目所提供的有关信息，将答案填入这些行与列之中，每个白色方格中只能填入一个字。一般地说，题目给出的每一条信息就是对应的一行或一列的解题线索。在行与列交叉的地方，玩家必须保证在交叉的方格中填入的字同时满足题目中对行与列的要求。（详见填字游戏）
# 相关
最常被引用的结果之一设计神喻。假想你有一个魔法机器可以解决单个问题，例如决定一个给定的数字是否为质数，但可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P = NP 和 P ≠ NP 二者都可以证明。这个结论的后果是，任何可以修改来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。
如果这还不算太糟的话，1993 年 Razborov 和 Rudich 证明的一个结果表明，给定一个特定的可信的假设，在某种意义下 “自然” 的证明不能解决 P = NP 问题。这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。这实际上也是为什么 NP 完全问题有用的原因：若有一个多项式时间算法，或者没有一个这样的算法，对于 NP 完全问题存在，这将用一种相信不被上述结果排除在外的方法来解决 P = NP 问题。P=NP 问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有 P 中的语言可以用一阶逻辑加上最小不动点操作（实际上，这允许了递归函数的定义）来表达。类似地，NP 是可以用存在性二阶逻辑来表达 — 也就是，在关系、函数、和子集上排除了全域量词的二阶逻辑。多项式等级，PH 中的语言对应与所有的二阶逻辑。这样，“P 是 NP 的真子集吗” 这样的问题可以表述为 “是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？” [4]
普林斯顿大学计算机系楼将二进制代码表述的 “P=NP?” 问题刻进顶楼西面的砖头上。如果证明了 P=NP，砖头可以很方便的换成表示 “P=NP！”。康奈尔大学的 Hubert Chen 博士提供了这个玩笑式的 P 不等于 NP 的证明：“反证法。设 P = NP。令 y 为一个 P = NP 的证明。证明 y 可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为 P = NP，该证明 y 可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。
# 最新情况
2010 年 8 月 6 日，HP LAB 的 Vinay Deolalikar 教授宣布证明了 P!=NP，证明文章已经发送到该问题各相关领域专家手中，等待检验，在他的主页上，证明过程已经公布（PDF 格式共 103 页），但在 8 月 15 日，人们关于论文的看法 —— 即证明不能成立 —— 已经趋于稳定（当然这不能排除大家都同时犯了错误的可能性），随后的发言越来越多地集中于更抽象的层面，并且至今仍在继续。
论 NP=P？
NP=P，概括的说就是 3 句话：
1. 任意简单无向图的最大团问题等于其对应的 “任意两个顶点的距离不大于 2 的图”—— 可以称之为理想图的最大团问题；
2. 任意理想图的图着色问题是多项式时间问题；
3. 任意理想图，其图着色问题可在多项式时间内转换为它的最大团问题。
证明大纲：
定理 1. 设 G=（V,E）是简单无向图，va、vb 是 G 中距离大于 2 的两个顶点，E'=E∪{（va，vb）}，则 G'=(V，E') 与 G 有相同的最大团。
证明：显然。
推论：对任意简单无向图 G=（V,E），存在简单无向图 G'=(V，E')，满足：
（1）E⊆E'；
（2）G' 中任意两个顶点的距离不大于 2；
（3）G' 与 G 有相同的最大团。
定理 2. 设 G=（V,E）是 n 阶简单无向图，n≥3，G 中任意两个顶点的距离不大于 2，则存在 n 的多项式时间算法，可在该算法下，解决 G 的图着色问题，即确定 G 的顶点色数。
证明思路与算法：易知 G 是 k - 部图（不一定、也无须是完全 k - 部图）。
算法：设 v 是 G 中度最大的顶点，显然 v 的邻点应该与 v 着色不同。在距离 v 为 2 的
顶点中，依次选取 G 中度最大且互不相邻的顶点，得到包含 v 的一个极大独立集 V1，
设 V=V1∪V2,V1∩V2=Ø，G 去掉 V1 中所有顶点（及其关联边）得到图
G2=(V2，E2)。则可以证明 G2 的顶点色数比 G 的顶点色数小 1；且 G2 去掉度
小于 2 的顶点（若这样的顶点存在）后，任意两个顶点的距离也是不大于 2 的。
由递归关系可知 G 的顶点色数可以在 n 的多项式时间内确定。
定理 3. 设 G=（V,E）是 n 阶简单无向图，n≥3，G 中任意两个顶点的距离不大于 2，则 G 的图着色问题（顶点色数问题）可以在 n 的多项式时间内转换为 G 的最大团问题。
