Class NPC Existence of NPC problem NPC=(L in NP: L'S, L for every L' in NP) Circuit satisfiability:【芯片满足性问题】 NP-Hard: ifL's L for every L' in NP,we Input n Boolean variables after a sequence of call L is NP-hard Boolean operations it outputs a value from Theorem344 If any one of the NPC f0, 11, if there exists a input such that its output say the circuit is satisfiable problem is belong to P, then P=NP Circuit-SAT=(<C> C is satisfiable boolean Theorem Circuit-SAT is belong to npc 清华大学宋域恒 请华大学宋恒 NP-completeness proofs Lemma34. 8 证明 circuit-satisfiability问题是NPC问 ·如果L是一个语言,如果存在一个L属于 题,依赖我们是否能够证明对于所有属 NPC,且满足L’≤L,则L是NP一难的 于NP的语言L都有:L≤ Circuit-SAT,其 ( NP-hard),如果进一步有L是NP则L属 证明超出了我们的课程的内容。 于NPC ·那么对于一般问题的NP完全是如何证明 ·证明:利用定义可以证明 的?这里我们把其中的过程做个介绍: 清华大学末斌恒 请华大学宋恒 般证明语言L是NPC的步骤 Formula satisfiability ·证明L属于NP Language SAT is defined as ·选取一个已知的NPC语言L SAT的实例是一个逻辑公式中,其构成如下 ·找到一个算法f使得f将L的每一个属于 1.n布尔变量:x1x2x3x 0,1}*实例x映射到L的实例fx) 2.m布尔运算符:and、or、not、 mplication、 if and only if(-,∧,V,→),)和 证明函数满足x属于L等价于f(x)属于 3.括号(没有多余括号) L对于所有属于{0,1}*的x都成立 我们可以证明SAT属于NPC【Cook定 ·证明计算f的算法是多项式的 理】 清华大学末域恒 请华大学宋8 清华大学 宋斌恒 43 Class NPC • NPC={L in NP: L’ ≤p L for every L’ in NP} • NP-Hard: if L’ ≤p L for every L’ in NP, we call L is NP-hard • Theorem34.4 If any one of the NPC problem is belong to P, then P=NP 清华大学 宋斌恒 44 Existence of NPC problem • Circuit satisfiability:【芯片满足性问题】 – Input n Boolean variables after a sequence of Boolean operations it outputs a value from {0,1}, if there exists a input such that its output is one we say the circuit is satisfiable. • Circuit-SAT={<C>:C is satisfiable boolean combinational circuit} • Theorem Circuit-SAT is belong to NPC 清华大学 宋斌恒 45 NP-completeness proofs • 证明 circuit-satisfiability 问题是NPC问 题，依赖我们是否能够证明对于所有属 于NP的语言L都有： L ≤p Circuit-SAT, 其 证明超出了我们的课程的内容。 • 那么对于一般问题的NP完全是如何证明 的？这里我们把其中的过程做个介绍： 清华大学 宋斌恒 46 Lemma34.8 • 如果L是一个语言，如果存在一个L’属于 NPC，且满足 L’ ≤p L，则 L是NP－难的 （NP-hard）,如果进一步有L是NP则L属 于NPC。 • 证明：利用定义可以证明 清华大学 宋斌恒 47 一般证明语言L是NPC的步骤 • 证明L属于NP • 选取一个已知的NPC语言L’ • 找到一个算法f使得f将L’的每一个 属于 {0,1}*实例x映射到 L的实例 f(x). • 证明函数f满足 x 属于 L’ 等价于 f(x) 属于 L对于所有 属于{0,1}*的x都成立 • 证明计算f的算法是多项式的 清华大学 宋斌恒 48 Formula satisfiability • Language SAT is defined as: – SAT的实例是一个逻辑公式φ，其构成如下 1. n布尔变量：x1,x2,x3,…xn. 2. m布尔运算符：and、or、not、 implication、if and only if(¬,∧,∨,→,↔)和 3. 括号（没有多余括号） ¾ 我们可以证明SAT属于NPC【Cook定 理】