南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）NP完全理论初步

计算机问题求解一论题4.7 NP完全性 陶先平 2017年4月24日

计算机问题求解—论题4.7 NP完全性 陶先平 2017年4月24日

问题1：这个定理想说明的道理是什么？ Lemma 34.1 Let O be an abstract decision problem on an instance set I,and let el and e2 be polynomially related encodings on I.Then,e1(O)EP if and only if e2(O)E P. For some set I of problem instances,we say that two en- codings e and e2 are polynomially related if there exist two polynomial-time com- putable functions f12 and f21 such that for any i 1,we have fi2(e1(i))=e2(i) andf21(e2(i)=e1(i).5

问题1：这个定理想说明的道理是什么？

Reduction yes instance a polynomial-time instance B polynomial-time >yes ofA reduction algorithm of B algorithm to decide B no no polynomial-time algorithm to decide A it provides us a way to solve problem A in polynomial time: 1.Given an instance o of problem A,use a polynomial-time reduction algorithm to transform it to an instance B of problem B. 2.Run the polynomial-time decision algorithm for B on the instance B. 3.Use the answer for B as the answer for a

Reduction

问题2：A和B问题，哪个可能更容易？为 什么？ In other words,by"reducing" solving problem A to solving problem B,we use the "easiness"of B to prove the “easiness”ofA

问题2：A和B问题，哪个可能更容易？为 什么？

问题3： ·算法A接受一个语言和算法A判定一个语言有什么区别？ The language accepted by an algorithm A is the set of strings L={x E{0,1):A(x)=1,that is,the set of strings that the algorithm accepts. A language L is decided by an algorithm A if every binary string in L is accepted by A and every binary string not in L is rejected by A. to accept a language,an algorithm need only produce an answer when provided a string in L,but to decide a language,it must correctly accept or reject every string in{0,1}

问题3： • 算法A接受一个语言和算法A判定一个语言有什么区别？

P类问题的定义： P=L 0,1*:there exists an algorithm A that decides L in polynomial time. 问题4：这两种P类问题的定义等价吗？ Theorem 34.2 P={L:L is accepted by a polynomial-time algorithm}

P类问题的定义： 问题4：这两种P类问题的定义等价吗？

In fact,P is also the class of languages that can be accepted in polynomial time. Theorem 34.2 P={L:L is accepted by a polynomial-time algorithm}. •证明： ·为何我们只需证明被接受的语言（问题）一定可 以被判定？ ·How to do it? 用接受这个语言的算法A来构造判定这个语言的算法A' 多项式算法A=>最多cnk步执行=>将这cnk步看做算法A'=>A'可以在cnk内对输入x进行判定

•证明： •为何我们只需证明被接受的语言（问题）一定可 以被判定？ •How to do it? 用接受这个语言的算法A来构造判定这个语言的算法A’ 多项式算法A=>最多cnk步执行=>将这cnk步看做算法A’=>A’可以在cnk内对输入x进行判定

havior of A.If A has accepted x,then A'accepts x by outputting a 1.If A has not accepted x,then A'rejects x by outputting a 0.The overhead of A'simulating A 这里面隐含了接受和判定的细微区别。你能解释一下吗？

这里面隐含了接受和判定的细微区别。你能解释一下吗？

问题5：我们为什么要引入“多项式时间 验证”某个语言（问题）？ We define a verification algorithm as being a two-argument algorithm A,where one argument is an ordinary input string x and the other is a binary string y called a certificate.A two-argument algorithm A verifies an input string x if there exists a certificate y such that A(x,y)=1.The language verified by a verification algorithm A is L={x∈{0，l1}*:there exists y∈0，l}*such that A(x,y)=}· 这里的所有概念，似乎都和问题复杂度，特别是超多项式复 杂度问题无关

问题5：我们为什么要引入“多项式时间 验证”某个语言（问题）？ 这里的所有概念，似乎都和问题复杂度，特别是超多项式复 杂度问题无关

NP复杂度类问题 The complexity class NP is the class of languages that can be verified by a poly- nomial-time algorithm.8 More precisely,a language L belongs to NP if and only if there exist a two-input polynomial-time algorithm A and a constant c such that L=x0,1*:there exists a certificate y with ly=(x) such that A(x,y)=1. We say that algorithm A verifies language L in polynomial time. 问题68这里的vcf9和⑧前面的vcf9,有什么区J?

NP复杂度类问题 问题6：这里的verify和前面的verify，有什么区别？