NP类问题：多项式时间可以被证明的问题。
P类问题：多项式时间内可以解决的判定性问题。
所有的P类问题都是NP类问题。 P ⊆ N P P \subseteq NP P⊆NP（但是是否是真子集目前仍是开放问题）NPC类问题：(NPC, non-deterministic polynomial-time complete problem)非确定多项式时间完成问题
NPC类问题 = NP+（NP-hard）介绍几个相关概念： 1.判定问题与最优化问题： - 现实中很多问题都是 最优化问题 ，希望找到一个具有最佳值的可行解。 - NP 完全性不适合直接应用于最优化问题，而适用于 判定问题 ：判断一个问题的答案“是” 或“否”（即程序给出“1” 或“0” 的输出）。
最优化问题->判定问题：给待优化的值加一个界，就可以将给定的最优化问题转换为一个相关的判定问题了。判定问题->最优化问题：从 n = ∣ V ∣ n=\lvert V \rvert n=∣V∣开始，逐渐给最短路径加界限，例如逐个求解 k = n , k = n − 1 , … , k = 0 k=n,k=n-1,…,k = 0 k=n,k=n−1,…,k=0的PATH 问题。判定问题更容易一些，至少不会更难。如果知道判定问题是困难的，相应的优化问题也是困难的。
2.归约： 对于两个判定问题A、B来说： 归约提供了一种在多项式时间内解决问题A的方法： 问题的实例指某一特定问题的输入。
那么将归约反证法应用到NPC问题的证明上就是：
如果我们可以证明一个问题是NPC问题，那么就可以 说明其不易处理性，最好的办法就是开发一种近似算法，而不是寻找求得问题确切解的一种快速算法。
那么怎么证明NPC问题呢？
形式化定义“问题”、复杂类P（它包含了多项式时间内可解的判定问题）
为什么多项式时间可解问题是易处理问题？ 一旦某个问题的第一个多项式时间算法被发现后，往往跟着就会发现更为有效的算法。在一个模型上用多项式时间可解问题，在另一个模型上也可以在多项式时间内结解决。封闭性。对多项式时间算法进行加法、乘法和组合运算，其结果的运行时间也是多项式的。 抽象问题 为了理解多项式时间可解问题类，必须对所谓的“问题”进行形式化定义。 抽象问题 Q 是问题实例集 I 与问题解集 S 上的二元关系。对于NPC问题来说，既判定问题中，我们可以把抽象的判定问题看做是从实例集I映射到解集｛0，1｝上的一个函数。有些不是判定问题的抽象问题，既最优化问题，通过为将被优化的值增加一个界限，优化问题可改造成判定问题。若能证明判定问题是难的，则原优化问题也是难的。 编码 用计算机程序来求解抽象问题，必须用一种程序能理解的方式来表示问题。抽象对象集S 的编码是从S 到二进制串集合的一个映射e。 eg: 将自然数 N = { 0 , 1 , 2 , 3 , 4 … } N = \{0,1,2,3,4…\} N={0,1,2,3,4…}编码为串 { 0 , 1 , 10 , 11 , 100 , … } \{0,1,10,11,100,…\} {0,1,10,11,100,…}
具体问题是实例集为二进制串集合的题。(将问题实例的编码作为输入。)
如果对某具体问题存在常数k 和算法A，使得A 在时间 O ( n k ) O(n^k) O(nk)内解决了该具体问题，那么称该具体问题是多项式时间可解的。
复杂类P定义为多项式时间可解的具体判定问题的集合。
利用编码将抽象问题映射到具体问题上，具体问题与抽象问题产生同样的解。也希望通过编码的方式把多项式时间可解性的定义从具体问题扩展到抽象问题，但是实际上求解问题的效率依赖于问题的编码。so 对抽象问题的编码相当重要。一元编码只需线性时间的算法，若采用二进制编码，则可能需要指数时间(伪多项式时间)。若存在多项式时间算法A，使得对任意给定的输入 x ∈ { 0 , 1 } ∗ x \in \{0,1\}^* x∈{0,1}∗，A产生输出 f ( x ) ∈ { 0 , 1 } ∗ f(x) \in \{0,1\}^* f(x)∈{0,1}∗，称函数 f : { 0 , 1 } ∗ f:\{0,1\}^* f:{0,1}∗-> { 0 , 1 } ∗ \{0,1\}^* {0,1}∗是多项式时间可计算的函数。
设 I 是问题实例的集合， e 1 e_1 e1和 e 2 e_2 e2是两种编码，如果存在两个 多项式时间可计算的函数 f 12 f_{12} f12 和 f 21 f_{21} f21，使得对任意 i ∈ I i \in I i∈I, 有 f 12 ( e 1 ( i ) ) = e 2 ( i ) f_{12}(e_1(i)) = e_2(i) f12(e1(i))=e2(i)且 f 21 ( e 2 ( i ) ) = e 1 ( i ) f_{21}(e_2(i)) = e_1(i) f21(e2(i))=e1(i)，那么称 e 1 e_1 e1 和 e 2 e_2 e2 是多项式相关的。
引理：
因此以后的分析均假定一个整数的编码与其二进制表示是多项式相关的，称为其标准编码。G 的标准编码记为 ⟨ G ⟩ ⟨ G ⟩ ⟨G⟩。
形式语言体系 概念 字母表 ∑ \sum ∑：符号的有限集。语言 L L L：由 ∑ \sum ∑中符号组成的串的任意集合空串： ε \varepsilon ε空语言： ϕ \phi ϕ所有串构成的语言： ∑ ∗ \sum^* ∑∗， L ⊆ ∑ ∗ L\subseteq \sum^* L⊆∑∗语言的交、并，与集合论相同。语言的补： L ‾ = ∑ ∗ − L \overline{L} = \sum^* - L L=∑∗−L两种语言 L 1 L_1 L1和 L 2 L_2 L2连结 L 1 L 2 L_1L_2 L1L2： L = { x 1 x 2 : x 1 ∈ L 1 且 x 2 ∈ L 2 } L = \{x_1x_2:x_1 \in L_1且x_2 \in L_2 \} L={x1x2:x1∈L1且x2∈L2}闭包： L ∗ = { ε } ⋃ L ⋃ L 2 ⋃ L 3 ⋃ … L^* = \{\varepsilon\}\bigcup L \bigcup L^2 \bigcup L^3 \bigcup … L∗={ε}⋃L⋃L2⋃L3⋃…其中 L k L^k Lk表示L自身连接k次接受：给定输入，输出为1拒绝：给定输入，输出为0判定：算法A输出A(x)=1或者A(x)=0。 语言的接受拒绝和判定，接受拒绝都是对给定的串给出答案就好，但是判定某一语言，必须正确的接受或者拒绝 { 0 , 1 } ∗ \{0,1\}^* {0,1}∗中的每一个串。。。。所以判定更难一些！停机问题存在接受算法，但不存在判定算法。 复杂类P的另外定义： P = { L ⊆ { 0 , 1 } ∗ ： 存 在 一 个 算 法 A ， 可 以 在 多 项 式 时 间 内 判 定 L } ｝ P = \{L \subseteq \{0,1\}^*：存在一个算法A，可以在多项式时间内判定L\}｝ P={L⊆{0,1}∗：存在一个算法A，可以在多项式时间内判定L}｝前面的定义：复杂类P定义为多项式时间可解的具体判定问题的集合。定理34.2 { P = L : L 由 某 个 多 项 式 时 间 算 法 接 受 } \{P = L:L由某个多项式时间算法接受\} {P=L:L由某个多项式时间算法接受}判定 ⊂ \sub ⊂接受，判定必然可接受。定义关于判定问题的NP类，这些问题解可以在多项式时间内进行验证，形式化提出 P ≠ NP 这一问题。
哈密顿回路问题 H A M − C Y C L E = { < G > ： G 是 哈 密 顿 图 } HAM-CYCLE = \{<G>：G是哈密顿图\} HAM−CYCLE={<G>：G是哈密顿图} 验证语言： L = { x ∈ { 0 , 1 } ∗ ： 存 在 y ∈ { 0 , 1 } ∗ ， 使 得 A ( x , y ) = 1 } L = \{x \in \{0,1\}^*：存在y \in \{0,1\}^*，使得A(x,y)=1\} L={x∈{0,1}∗：存在y∈{0,1}∗，使得A(x,y)=1} L ∈ N P L \in NP L∈NP 时，当且仅当存在具有两个输入的多项式时间算法A和常数c，使得： L = { x ∈ { 0 , 1 } ∗ ： 存 在 证 书 y 且 ∣ y ∣ = O ( ∣ x ∣ c ) 使 得 A ( x , y ) = 1 } L = \{x \in \{0,1\}^*：存在证书y且|y|=O(|x|^c)使得A(x,y)=1\} L={x∈{0,1}∗：存在证书y且∣y∣=O(∣x∣c)使得A(x,y)=1}，称算法A在多项式时间验证语言L。 H A M − C Y C L E ∈ N P HAM-CYCLE \in NP HAM−CYCLE∈NP 复杂类NP 复杂类NP是能被一个多项式时间算法验证的语言类。 L ∈ P ， 则 L ∈ N P L \in P，则L \in NP L∈P，则L∈NP。如果存在一个多项式时间的算法来判定 L，那么只要忽略任何证书，并接受那些确定属于L的输入串，就可以很容易的把该算法转化为一个两参数的验证算法。因此 P ⊆ N P P \subseteq NP P⊆NP。关于NP的思考： P ⊆ N P P \subseteq NP P⊆NP验证比判定容易讨论如何通过多项式时间的归约来比较各种语言的相对难度。定义NP完全语言，简要证明CIRCUIT-SAT语言是NP完全的。
可归约性 如果存在多项式时间可计算的函数 f : { 0 , 1 } ∗ f :\{0, 1\}^∗ f:{0,1}∗ -> { 0 , 1 } ∗ \{0, 1\}^* {0,1}∗，使得对所有 x ∈ { 0 , 1 } ∗ x \in \{0, 1\}^* x∈{0,1}∗， x ∈ L 1 x \in L_1 x∈L1 当且仅当 f ( x ) ∈ L 2 f(x) \in L_2 f(x)∈L2，那么称语言 L 1 L_1 L1多项式时间可归约到语言 L 2 L_2 L2，记为 L 1 ≤ P L 2 L_1 \leq _P L_2 L1≤PL2。这时，称函数 f f f 为归约函数；称计算 f f f 的多项式时间算法 F F F 为归约算法。 NP完全语言 也就是说NP完全 = NP + 所有NP都可以归约为L（L是最难的）满足性质2不满足性质1，也就是比所有NP都难的问题，称为NP难。定理34.4（没看懂） 电路可满足问题是NPC的 证明电路可满足性问题是NP类证明电路可满足性问题是NP-hard讨论如何利用归约方法，更简便地证明其他以一些问题也是NP完全问题。通过证明两个公式可满足性问题是NP完全的，对归约方法加以说明。
证明语言L是NP完全的方法： 证明 L ∈ N P L \in NP L∈NP。（L是NP的）选择一种已知的NP完全语言 L ′ L' L′。描述计算函数 f f f的一个算法 F F F，该函数把 L ′ L' L′的每个实例映射成L的实例。证明函数 f f f满足： x ∈ L ′ x \in L' x∈L′当且仅当 f ( x ) ∈ L f(x)\in L f(x)∈L对所有 x ∈ { 0 , 1 } ∗ x \in \{0,1\}^* x∈{0,1}∗成立。（ L ′ L' L′可归约为 L L L）证明计算 f f f的算法 F F F具有多项式运行时间。(归约算法多项式时间)其他一些NP完全问题 NP完全性证明结构，所有的证明最终都是通过对CIRCUIT-SAT的NP完全性归约得到的。
团问题（clique）顶点覆盖问题（vertex-cover）哈密顿回路问题(HAM-CYCLE)子集合问题(subset-sum)旅行商问题