计算机问题求解 一论题4.9NP完全性 陶先平 2019年5月15日
计算机问题求解 —论题4.9 NP完全性 陶先平 2019年5月15日
问题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判定一个语言有什么区别？