计算机问题求解—论题7 NP完全性.pptVIP

计算机问题求解—论题4.7NP完全性 陶先平 2017年4月24日 问题1：这个定理想说明的道理是什么？ Reduction 问题2：A和B问题，哪个可能更容易？为什么？ 问题3： 算法A接受一个语言和算法A判定一个语言有什么区别？ P类问题的定义： 问题4：这两种P类问题的定义等价吗？ 证明： 为何我们只需证明被接受的语言（问题）一定可以被判定？ How to do it? 用接受这个语言的算法A来构造判定这个语言的算法A’ 多项式算法A=最多cnk步执行=将这cnk步看做算法A’=A’可以在cnk内对输入x进行判定 这里面隐含了接受和判定的细微区别。你能解释一下吗？ 问题5：我们为什么要引入“多项式时间验证”某个语言（问题）？ 这里的所有概念，似乎都和问题复杂度，特别是超多项式复杂度问题无关。 NP复杂度类问题 问题6：这里的verify和前面的verify，有什么区别？ P，NP，co-NP的关系谜团 问题7：你能从这几种猜想中得到什么确定性的信息？ 问题8：我们引入NPC，为什么？ 一方面： 另一方面： 又见归约！ 问题9：你能说说看，“语言L1可以函数f作用下，被多项式归约到语言L2”这句话背后隐含了哪些内容？ 构造A1算法的目的是什么？ 归约！ 又见归约！ 问题10：这个引理是NPC定义的基石。你能解释为什么是这样的吗？ 问题11：为什么只要找到一个NPC问题的P算法，所有的NP问题都可以多项式求解？ 问题12：从NPC的定义中看，证明一个问题(语言)是NPC有多难？ 问题12: 请回答： 为什么第一个NPC问题被证明是非常有价值的？ 哪一个问题是第一个被证明为NPC问题？ C-SAT问题： 第一个被计算机科学家从定义开始严格证明为NPC的难题！ 证明框架 C-SAT∈NP？ 可验证 多项式 L是NP，存在多项式验证算法A，对于任意的01串x，存在证书y(O(nk))： A(x,y)=1 最重要也是几乎唯一的线索 如何利用这个线索，构造多项式算法F，实现归约函数f： 将x映射为一个电路？ 算法A的运算过程可以被理解为格局的转换，组合电路的作用 证明过程的几个要点 内存格局/配置(Configuration)是系统内存的一个快照 01位串而已 格局之间的转换configi到configi+1是由(验证)算法驱动的。 但也可以被理解为一个组合逻辑电路C在输入configi时，输出configi+1 x可以被接受，就是存在一个证书y，L的验证函数A(x,y)=1 A的验证步骤中产生的格局变迁，决定了：一定存在一个电路片段，使然！ 归约算法，利用了这个电路片段的存在性，构造了L中任意x和完整电路C的映射！ 证明概要： F：从任意的01串x出发，构造对应的电路C 构造C’=M1||M2||…||MT(n) 电路的输入：内存格局的初始值 电路的输出CT(n) 从C’中改造得到C 将C’的输入中A、PC、x、内存固化为它们的初始值，仅保留整数y 保留C’的输出中的A(x,y)值，其它全忽略 C(y)=A(x,y) f(x)=C 问题13：如果每个NPC都这样证明，不够高效。你能解释这个定理在这个问题上的作用吗？ 问题14：从这个定理出发，你能找到更高效的、一般性的NPC证明方法吗？ NPC证明方法： Moreover, as we develop a catalog of known NP-complete problems, we will have more and more choices for languages from which to reduce. Open topics: 在阅读资料JH中，作者是用 来定义NP的。请你说说两种定义方法是一致的吗？为什么？ 证明旅行商问题是NPC问题