计算机问题求解 一论题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难)，证明哪个问题难？