归约
设计一个函数f(x)，把问题A的输入转换成问题B的一个输入，这样就能用问题B的解法来求解。（输出真或假）
转换函数f(x)的设计必须要保证问题B的输出结果和相应的问题A上的答案保持一致。
这样就是一个归约技术，将这个问题转换为类似的其他问题。
多项式归约
归约是指A的输入x经过f(x)转换成B的输入x’，所谓多项式归约是指转换函数f(x)不能太复杂，需要在多项式时间内完成。如果是指数级或其他复杂度就没有意义了。
符号是一个小于等于号加上下标一个p代表多项式。
A多项式归约B，意味着问题B至少和求解问题A一样难，意义跟小于等于号类似。
多项式归约实际是用来比较解决两个问题的难度大小关系。
多项式归约的性质
建立多项式可解性
B多项式可解则A也多项式可解。
建立建立难解关系(intractability)
A多项式不可解则B也多项式不可解。
建立等价性
A、B相互归约，则 A B两个问题等价。
多项式归约的方法
具体如何做多项式归约呢？
- 通过简单等价性
- 通过一般情况归约
- 通过编码
简单等价性
这里举一个例子，一个问题是独立集问题，一个问题是顶点覆盖问题。
独立集：求一个子集S，顶点数>=k，其各顶点之间相互独立，没有边相连。
（假装有图）
k=6: 存在
k=7：不存在
顶点覆盖：求一个子集S，顶点数<=k，
（假装有图，跟上一张图一样）
k=4:存在
k=3：不存在
两个问题是一个等价问题，解是互补关系。
证明略。
一般情况归约
这里同样举两个例子。
集合覆盖(set cover)
设有一个所有元素的集合U，U有S1,S2,S3...Sm的元素子集，是否存在<=k个子集的集合，他们的并集就是U。
顶点覆盖问题
如上。
这两个问题之间可以相互归约，顶点覆盖问题可以看做集合覆盖问题的特殊情况。
即：U是所有边的集合，每个子集相当于一个顶点，子集内是该顶点关联的边。
编码
问题A和问题B的形式上差距很大，需要通过零件编码(encode with gadgets)？
同样举两个例子。
布尔公式可满足问题
布尔变量的析取构成子句，子句的合取构成公式。
问题是：是否存在一组布尔变量满足公式为真。
这个问题非常复杂，所以有一个简化的问题：每个子句含有三个布尔变量，求公式的可满足解。 这就是3-SAT可满足问题。
独立集问题
如上。
两个问题看起来差距很大（不是看起来好吧），但其实也是可以相互归约的。
将3-SAT问题归约成一个图的独立集问题
具体怎么编码呢？通过布尔公式构造一个图，图怎么构造呢？公式是由多个子句构成，每个子句构成一个子图，所以每个子图是一个三角形，有三个顶点对应三个布尔变量。将每个变量和它的否定之间加一条边，这样就把边加上去了。
（假装有图）
寻找可满足解实际就是独立集问题，独立集问题中的k取公式中子句的数量，通过这样一个构造方式，3-SAT问题就被归约成了一个图的独立集问题。
我们需要证明这个归约过程是有效的：证明：S如果是图里的一个独立集<--->可以找到一个可满足解
证明
S如果是一个独立集，那么S在这个图里，每个三角形里最多包含一个顶点，否则不是独立集。将所有这些点设置为true，则这个公式一定可以满足。
反过来，如果是一个可满足解，在每个子句里，选择一个为true的文字量，将三角形里对应的点选出来，这些点union起来就是一个独立集。
有了这个归约技术以后，则可以进行问题之间难度的比较关系。归约满足传递性。
NP完全性
有了多项式归约这个基础，就可以解释NP完全性。之前讨论算法时，经常会讨论到可以把一个很复杂的问题用一个巧妙的多项式方法解决。实际上，有很多实际的问题，以目前的技术是很难给出有效的多项式解法，这些问题就是NP完全问题，代表困难问题。比如0-1背包问题等。
特别关心哪些问题是属于NP完全问题，要了解问题的难度，可以设计启发式的算法、近似解、使用指数级复杂度算法。。
接下来讨论三类问题
P类问题，NP问题，NP完全问题。
Class P P类问题是代表一类问题，这个P代表Polynomia多项式,所有多项式时间内可解的问题都属于P类问题。比如常数时间，分治法中的求中位数等。
不属于P类问题的问题有intractable和unsolvable，比较经典的不可解问题是图灵停机问题，halting problem，给你任意一个算法和它的输入，设计一个算法判断它是否是无限循环，能否终止。
有些问题属于难处理问题，难到什么程度呢？一个叫NP完全问题 一个叫NP困难问题。
N:Nondeterministic，非确定性，算法的执行过程是不确定的。如果一个算法由两个步骤构成的，生成一个随机解certificate，猜出一个随机解，第二步进行验证猜的解对不对。这样一个算法称为非确定性算法，第一个阶段是不确定的，第二个阶段是确定的。
P：polynomia，验证阶段是多项式的。
P和NP是否相等？is P = NP ?
any problem in P is also in NP
NP属于P还没有证明。
NP完全问题，NP问题里最难的问题，大多数实际问题要么是P问题要么是NP完全问题，但P和NP都只是所有实际问题的子集。
B是NP完全问题，(1)B是NP问题，(2)所有属于NP问题的A 都可以归约成问题B。
如果B只满足(2)，则B是NP-hard问题。
目前没有人证明NP是不能多项式可解，也没人证明NP是多项式可解。
网友评论