此文自阅读《Intoduction to Algorithm》总结 or 所思所获。
引言
NP问题大家应该有所耳闻，都说是非多项式时间内可以解决的问题。在这里，笔者仅以多次翻阅《算法导论》的理解来用尽量通俗的语言来描述这一美妙至极的问题。
为甚么要研究NP问题?
研究NP问题从算法复杂度方面给了我们对于计算机所能解决的问题直观的认识。一般来说，计算机能解决的复杂的实际问题也是我们对于量级的问题的极限了。
故如果能够窥探一隅，也是收益颇丰的。
实际的角度来说，对于一个问题，作为一介平凡百姓的角度来说，如果被证明是NPC问题(暂且把它当作人类还没有方法解决的问题)，那便至少不必大费宝贵的时间于其中。
哲学的角度来说，其中的美妙之处更是难以言尽…人类的极限是什么呢？
什么是P/NP问题?
首先要引入对于两类问题的归类:
- 判定问题（decision problem）: 问题的解答仅为是与否的一类问题
- 最优化问题（optimization problem）: 求解问题最优解的一类问题
接下来我们将主体说明这几类问题，称为P问题，NP问题与NPC问题。
准确的说，
- P问题（polynomial time）：在多项式时间内可以求解的判定问题
- NP问题（nondeterministic polynomial time）：在多项式时间内可以判断（验证）一个解是否成立的判定问题
- NPC问题（NP完全问题）：NP类问题中最为难解的问题
这里需要说明的几点：
- 最优化问题往往是有趣的问题，而一般来说，判定问题是最优化问题的基础，为什么这么说？因为如果解决了最优化问题，判定问题自然能够轻松解决。（这里说的仅是判定最优解的一类问题，而不是要求求出比如求解路径一类的问题）
- NPC问题与NP问题与区分：NP问题并不是都是难解问题，至少显然P $\subseteq$ NP, 因为显然多项式内能够求解的问题，自然能够判断。更为本质的区别，之后会提及。
- 关于NP-hard问题：应该说是比NPC问题更难的问题，未必在多项式时间内可以验证一个解的问题，故NP-hard $\not \subseteq$ NP。
如何研究NP问题
《算法导论》上利用归约方法来判定一个问题是否属于NPC问题。
归约：问题A的任意实例问题能够在多项式时间内转换为问题B的某个实例。并且两者是“等价”，即问题B的对应实例的解可以转化为问题A的对应实例的解。
NP完全问题正式定义是，若任何NP问题均能够归约于某类问题，这类问题被称为NPC问题。因此定义前提下，NP完全问题是NP问题中最难的一类问题。
而证明一个问题是NPC问题的方式，证明存在某个NPC问题能够归约于该问题。
附：P/NP问题的研究历史算来不长，在20世纪60年代才由一些计算机科学家提出，而NP完全问题的概念更是在1971年才由科学家Cook提出，并给出了公式可满足性问题和3-CNF可满足性问题的第一个NP完全性证明。此后有越来越多问题被证明是NP完全的，极大促进了对于此类问题的研究发展。而对于NP问题是否能在多项式时间内判断还是一个未解之谜，也使得P=NP?成为了“千禧年”问题之一。
多项式时间的严格定义
这一块是我读不懂的一块，主要涉及到形式语言和自动机原理，还有编码问题，其实仔细想想也能想到其缘由。
计算机能够表达的语言是建立编码之上的，而你描述的算法的运行是在计算机基础之上的，如何才能够确切的表示计算机多项式时间需要对这一块有严格的说明。
还望高人指点。（注：以后回顾时希望能够补上吧。）
几个NPC问题
公式可满足性问题
问题定义: 给定一个布尔公式，判定是否是可满足的。
CLRS说明: 大致证明意思应该是计算机电路即可以表示为布尔公式，而NP问题能够在计算机上多项式时间内验证，即可转换为对应的可满足性。3-CNF可满足性问题
问题定义: 给定的布尔公式是3-合取范式的形式，判定是否可满足:
$$(x_1 \lor \neg x_2 \lor \neg x_3) \land (x_3 \lor x_4 \lor \neg x_5)$$
如上式
CLRS说明: 可以证明任意布尔公式可以在多项式时间内转化为3-合取范式形式，通过变量代换可以得到。
具体的，显然，所有布尔公式都可以逐步用两两文字一一计算得到, 也就是能够形成一个二叉树的结构，左右儿子节点通过固定运算得到。 如何转化为3-合取范式(每个子句均是3个文字组成)? 很巧妙地，可以通过不断定义另一个文字替代这个文字运算后的结果。例如 $x_1 \lor x_2$，利用到$ y \leftrightarrow (x_1 \lor x_2) $， 这是一个3-合取范式，而之后用到$x_1 \lor x_2$时可以用 $y$ 代替。显然等价。
附：名词解释举例, 文字 (比如$x_1$) 子句 (比如$x_1 \lor \neg x_2 \lor \neg x_3$)团问题
规模为k的团: 一个图中的一个规模为k的完全子图
问题定义: 判定给定图中是否有规模为k的团 或者 求图最大团的规模
CLRS说明: 可以证明对于任何一个3-CNF公式满足性问题可以构造为一个图。如果这个公式由k个子句组成，并且是可满足的，则对应于该图的一个团。
想想如何构造顶点覆盖问题
版权声明：署名-非商业性使用-禁止演绎 | Creative Commons BY-NC-ND 3.0
博客链接：http://wsnpyo.github.io/
