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

计算机问题求解 一论题4.9NP完全性 陶先平 2021年5月7日

计算机问题求解 —论题4.9 NP完全性 陶先平 2021年5月7日

关于NP完全问题的2个直观理解 ·什么是NP完全问题： ·在多项式时间内可以“verifiable”的问题 ·什么是verifiable? ·给定一个certification,比如3SAT问题的一个变元赋值，验算其是否是可满足的！ ·为什么优化问题不能直接用NP完全性来考察？ ·比如最短哈密尔顿回路？ ·任意给一个certification,无法断定其是否最短！ ·但是有不少优化问题是“很难”的，怎么办？ ·优化问题和判定问题的“转化”定义 ·优化问题对应的判定问题“很难”=》优化问题也“很难

关于NP完全问题的2个直观理解 • 什么是NP完全问题： • 在多项式时间内可以“verifiable”的问题 • 什么是verifiable？ • 给定一个certification，比如3SAT问题的一个变元赋值，验算其是否是可满足的！ • 为什么优化问题不能直接用NP完全性来考察？ • 比如最短哈密尔顿回路？ • 任意给一个certification，无法断定其是否最短！ • 但是有不少优化问题是“很难”的，怎么办？ • 优化问题和判定问题的“转化”定义 • 优化问题对应的判定问题“很难”=》优化问题也“很难

问题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)E P 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 fi2 and f21 such that for any iI,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 i 什么叫 1. Given an instance o of problem 4.use a polynomial to transform it to an instance B of problem B. transform? 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 什么叫 transform？

问题2： 2.1A和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.2 reduce方法的更深用意在于证明某个问题有 多难（比如NPC难），证明哪个问题难？ instance a polynomial-time instance B polynomial-time yes yes ofA reduction algorithm of B algorithm to decide B no no polynomial-time algorithm to decide A

问题2： 2.1 A和B问题，哪个可能更容易？为什么？ 2.2reduce方法的更深用意在于证明某个问题有 多难(比如NPC难)，证明哪个问题难？

问题3： ·算法A接受一个语言和算法A判定一个语言有什么区别？ The language accepted by an algorithm A is the set of strings L={xE(0,1)*:A(x)=13,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：这个定理，想表达什么？ Theorem 34.2 P={L:L is accepted by a polynomial-time algorithm}

P类问题的定义： 问题4：这个定理，想表达什么？

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' 1)多项式算法A最多cnk步执行可以接受L的某个实例x 2)A'算法：接受任意的Σ*上的实例x,同样执行这cnk步，然后如果A接 受了x,A返回1，否则返回0 3)A'算法判定了L,并且是多项式时间算法

•证明： •为何我们只需证明被接受的语言（问题）一定可 以被判定？ •How to do it? 用接受这个语言的算法A来构造判定这个语言的算法A’ 1）多项式算法A最多cnk步执行可以接受L的某个实例x 2）A’算法：接受任意的Σ*上的实例x，同样执行这cnk步，然后如果A接 受了x，A’返回1，否则返回0 3）A’算法判定了L，并且是多项式时间算法

定理证明中有： 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. 这里面隐含了接受和判定的细微区别。你能解释一下吗？

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

问题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，l}*:there exists y∈{0，l}*such that A(x,y)=l}

问题5：我们为什么要引入“多项式时间 验证”某个语言（问题）？