• P类问题：在多项式时间内可以解决的问题。更确切的说，这些问题可以在时间 O(n) 内解决，其中 k 为某一常量， n 是此问题的输入的规模

• NP类问题：在多项式时间内可以被证明的问题。

  • 可被证明：即如果已知一个问题解的 证书，那么可以证明此问题在该输入规模下能在多项式时间内解决。如，对于 3-CNF 可满足性问题，一个证书可以是对一组变量的一个赋值。我们可以在多项式时间内检验这一赋值是否满足此布尔表达式。

• 所有的P类问题同时也是NP类问题，因为如果一个问题是P类问题，那么不用任何证书就可以在多项式时间内解决它。

• NPC类问题：NP完全问题

• 证明NPC

  • 判定问题与最优化问题
  • 归约

• 第一个NPC问题
  • 由于归约这一技巧依赖于条件”已知一个NP完全问题”才能去解决另一不同的NP完全问题,所以我们需要找到”第一个”NP完全问题.
  • 电路可满足性问题: 已知一个由AND, OR和NOT门所组成的布尔组合电路,我们希望知道这个电路是否存在一组布尔输入,能够使它的输出为1

多项式时间

• 抽象问题Q为在问题实例集合I和问题解集合S上的一个二元关系
• NP完全性理论把注意力集中在判定问题上,即那些解为 “是”或”否”的问题.
• 可以把抽象的判定问题看做是从实例集I映射到解集 {0, 1} 上的函数.
• “求解”某个抽象判定问题的计算机算法实际上是把一个问题实例的编码作为其输入,把以二进制串集合为实例集的问题称为 具体问题
• 复杂类P: 在多项式时间内可解的具体判定问题的集合

• 形式语言体系
• 定理: P = { L: L 能被一个多项式时间算法所接受 }

多项式时间的验证

• **NP包括了不属于P的语言

NP完全性与可归约性

语言L1在多项式时间内可以归约为语言L2

• NP完全性

通过直接证明对于任意语言L属于NP,都有L<=pCIRCUIT-SAT, 我们可以证明电路可满足性问题是NP完全的

NP完全性的证明

• 公式可满足性

证明: 1. SAT属于NP, 对于输入公式y,由它的一个可满足性赋值所组成的证书可以在多项式时间内得到验证. 2.电路可满足性问题的任何实例可以在多项式时间内归约为公式可满足性问题的一个实例.

• 3-CNF可满足性 (3-CNF-SAT)

NP完全问题

• 团问题(CLIQUE)