NP问题概述

P类问题：在多项式时间内可以解决的问题， 比如O(n)

NP类问题：给定一个证书，可以在多项式时间内验证此证书是否是问题的一个解的问题。比如，在哈密顿回路中，我们给出一个所有节点的序列，即证书，可以很容易在多项式时间内验证这个证书是否是一个哈密顿回路。

P问题一定是NP问题，如果一个问题是NP问题，那它是P问题？不知道

NPC问题（NP完全问题）

• 是一个NP问题
• 所有的NP问题都可以转化成此问题

NP难问题是NPC问题缺少第一个条件

判断是否NP问题

• 给出一个证书，可否在多项式时间内判断他是否是原问题的一个解
• 最优化问题需要转化为判断性问题（旅行商问题）

旅行商问题转化为：

• 此图中是否存在权重为1的回路？如果存在那就是旅行商问题的解

如果能够证明一个判断性问题为NP难时，显然原问题也是NP难问题。

基本概念：归约性

一个问题Q1可以归约为另外一个问题Q2，需要满足以下两个条件：

• 1、实例对应性：Q1的任意一个实例，通过函数f都可以转化成Q2的一个实例，且这个转化函数f必须为多项式时间；
• 2、输出一致性：归约后的输出和原来的输出一致，如果algo1是Q1的算法，algo2是Q2的算法，则在相同输入下，algo1(Q1) = algo2(Q2)

归约具有传递性，如果问题A归约到问题B，问题B归约到C， 那么问题A可归约到问题C

基本概念：归约证明

多项式时间内，Q1的实例可以通过函数f转化成Q2的一个实例

P问题的证明

2合取范式CNF的可满足行问题SAT

定义： 2CNF-SAT，2CNF是一个布尔表达式，其由子句的“与”组成，而每个子句都由两个文字的‘或’组成，这些变量及其‘否’为文字，两个文字构成了一个子句，2CNF的可满足性问题是指是否存在一个赋值，使得2CNF为真。