《SAT问题的NPC证明.ppt》由会员分享，可在线阅读，更多相关《SAT问题的NPC证明.ppt（72页珍藏版）》请在三一办公上搜索。
1、可满足性问题的NPC证明,-Cook定理,内容提要,证明思路总览证明中用到的知识 2.1 非确定图灵机 2.2 非确定图灵机的运转规则3.证明的详细过程 3.1 用或逻辑式表达运转规则 3.2 建立NP类问题到可满足性问题的多项式变换4.可能用到的知识附录,证明思路总览,根据NPC问题定义来证明 只要所有NPC问题均可在多项式时间内变换到SAT问题即可证明SAT问题为NPC.,任意的NP类问题,SAT问题,证明思路总览,如何证明所有NP类问题 SAT?然而，若将每个NP类问题都多项式变换到SAT问题是不现实的，所以要抽取NP类问题的共性，建立NP类问题的统一计算模型-非确定的图灵机（NDTM）
2、.,0,1,2,-1,-2,-3,-4,-5,3,4,5,6,7,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,证明思路总览,如何证明所有NP类问题 SAT?NP类问题的计算过程均可抽象为一个NDTM上的运作过程.因此，SAT的NPC证明等价于证明NDTM SAT.,0,1,2,-1,-2,-3,-4,-5,3,4,5,6,7,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,证明思路总览,如何证明NDTM SAT?只要找到多项式变换f；设一个NP类问题所对应语言的一个字符串为x，若x被NDTM接受，则对应SAT问题的例子f(x)回答为“是”
3、。,任意的NP类问题,SAT问题,证明思路总览,现整理证明的思路如下：,任意NP类问题,0,1,2,-1,-2,-3,-4,-5,3,4,5,6,7,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,语言,问题例子,字符串,对应,作为输入,建立图灵机的运作规则到SAT的多项式时间变换,问题得证,NP问题的统一模型,非确定图灵机计算模型,0,1,2,-1,-2,-3,-4,-5,3,4,5,6,7,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,NDTM的运转规则,非确定图灵机计算过程与DTM不同（两阶段）：猜想阶段 检验阶段,NDTM的运转规则
4、,0,1,2,-1,-2,-3,-4,-5,3,4,5,6,7,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,a,g,c,d,B,B,B,B,B,B,B,B,初始输入字符串x写入图灵机,猜想模块起作用，有限状态控制模块不起作用，从-1向左依次写入字符表中的任意多个任意字符,猜想阶段：,g,g,g,检验阶段：猜想模块不起作用，有限状态模块起作用,NDTM的运转规则,NDTM的运转规则被总结为6项：（1）初始时刻，M处于初态，读写头瞄准带格，x放置在 到 的带格中；而，,皆为空白。,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.
5、,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,NDTM的运转规则,NDTM的运转规则被总结为6项：（2）在每一时刻，M处于且仅处于一个状态。,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,NDTM的运转规则,NDTM的运转规则被总结为6项：（3）在每一时刻，读写头仅瞄准一个带格。,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,NDTM的运转规则,NDTM的
6、运转规则被总结为6项：（4）在每一时刻，每个带格恰好写有一个带符。,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,NDTM的运转规则,NDTM的运转规则被总结为6项：（5）在最后一步，若x被M接受，则当时状态为。,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,NDTM的运转规则,NDTM的运转规则被总结为6项：（6）M中一步计算的过程如下：,x,y,x,z,y,p,y,q,用或
7、逻辑式表达运转规则,或逻辑式中的布尔变量：(1)和状态相关的布尔变量：,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,第i步,用或逻辑式表达运转规则,或逻辑式中的布尔变量：(2)和读写头（Head）、带格相关的布尔变量：,0,1,2,-1,-2,-3,-4,-5,3,.,j,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,第i步,用或逻辑式表达运转规则,或逻辑式中的布尔变量：(3)和带格、带中字符相关的布尔变量：,0,1,2,-1,
8、-2,-3,-4,-5,3,.,j,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,第i步,j,(1)初始时刻的或逻辑式：,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,用或逻辑式表达运转规则,第0步,(2)在每一时刻，M处于且仅处于一个状态：,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,肯定处于一个状态,第i步,用或逻辑
9、式表达运转规则,(2)在每一时刻，M处于且仅处于一个状态：,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,读写头,n+1,b,b,b,A B m0,第i步,卡诺图,用或逻辑式表达运转规则,(3)在每一时刻，读写头仅瞄准一个带格：,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,用或逻辑式表达运转规则,最多在 步内判定一个猜想，而 表示还要多读一个空白符，从而M知道结束了,(3)在每一时刻，读写头仅瞄准一个带格：,0,1,2,
10、-1,-2,-3,-4,-5,j,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,读写头,n+1,b,b,b,A B m0,第i步,卡诺图,用或逻辑式表达运转规则,(4)在每一时刻，每个带格恰好写有一个带符:,0,1,2,-1,-2,-3,-4,-5,3,.,j,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,肯定有0s中的一个字符,第i步,用或逻辑式表达运转规则,(4)在每一时刻，每个带格恰好写有一个带符:,0,1,2,-1,-2,-3,-4,-5,3,.,j,.,n,.,.,.,.,.,.,.,.,有限状态控制器,读写头
11、,n+1,b,b,b,第i步,A B m0,卡诺图,用或逻辑式表达运转规则,(5)在最后一步，若x被M接受，则当时状态为:,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,第 步,用或逻辑式表达运转规则,(5)在最后一步，若x被M接受，则当时状态为:,0,1,2,-1,-2,-3,-4,-5,3,.,.,.,n,.,.,.,.,.,.,.,.,有限状态控制器,猜想模块,猜想头,读写头,n+1,b,b,b,第 步,用或逻辑式表达运转规则,用或逻辑式表达运转规则,(6)第i步到第i+1步计算
12、过程的或逻辑式:读写头指向的带格，字符才有可能改变,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:读写头没指向的带格，字符不可能改变,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:合并两卡诺图,A B m0,卡诺图,A B m0,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:合并两卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:书错了？！,我看了Cook71年原文，没有这个式子，关于(6)的式子，他仅举一例，一笔带过，只告诉大家有这个东西而已。,用或逻辑式表
13、达运转规则,(6)第i步到第i+1步计算过程的或逻辑式：,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:,两式相与，代入无误,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计
14、算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:合并四个卡诺图得,书上代入出错？！,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:或逻辑式推导,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:或逻辑式推导,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:合并四个卡诺图得,现在代入所有的取值都对,Cook71中和书上的式子一致，可能是他的笔误,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个
15、带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:合并四个卡诺图得,书上代入出错？！,用或逻辑式表达运转规则,(6)第i步到第i+1步计
16、算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化,A B m0,卡诺图,用或逻辑式表达运转规则,(6)第i步到第i+1步计算过程的或逻辑式:合并四个卡诺图得,书上代入出错？！,NDTM到
17、SAT问题的多项式变换,以上6组逻辑式集合的并，即为一个SAT问题的句子集。显然可以在多项式时间内得到该SAT问题，而且若NP类问题的例子回答为”是”，则对应的字符串x可被M接受，则对应的SAT问题有解。这就建立了一个NP类问题到SAT问题的多项式时间变换。从而问题得到证明；,第一章 数字逻辑基础,1.1 数制和BCD码,1.2 逻辑代数,1.3 逻辑函数的表示和化简,返回,第 1 章,上页,下页,数字电路电路的特点：1.所处理的数字信号只有两种取值(1、0）；2.电路抗干扰能力强；3.信息便于长期存储，便于计算机处理。,概述：,上页,下页,返回,第 1 章,翻页,逻辑代数运算规则,逻辑代数又
18、称布尔代数，是分析与设计逻辑电路的工具。逻辑代数表示的是逻辑关系，它的变量取值只有1和0，表示两个相反的逻辑关系。,第 1章,上页,下页,基本运算有：乘（与）运算、加（或）运算、求反（非）运算。,翻页,返回,1.2 逻辑代数,基本逻辑关系,上页,下页,第1章,返回,翻页,1.基本运算规则,上页,下页,第 1 章,A+0=A,A+1=1,A 0=0,翻页,返回,2.逻辑代数的基本定律,交换律：A+B=B+A,A B=B A结合律：A+(B+C)=(A+B)+C A(B C)=(A B)C,上页,下页,反演定理：,翻页,分配律：A(B+C)=A B+A C A+B C=(A+B)(A+C),返回,
19、第 1 章,上页,下页,第1章,本节结束,返回,1.3 逻辑函数的表示和化简,逻辑函数的表示方法,1.3.2 逻辑函数的化简法,上页,下页,第1章,返回,第1章,上页,下页,逻辑函数的表示方法,返回,翻页,逻辑式：用基本运算符号列出输入、输出变量间 的逻辑代数式,逻辑状态表：列出输入、输出变量的所有逻辑状态,卡诺图：与变量的最小项对应的按一定规则排列 的方格图,最小项是指所有输入变量各种组合的乘积项，输入变量包括原变量和反变量。例如，二变量A，B的最小项有四项：AB，AB,AB,AB;三变量的最小项有八项;依此类推，n 变量的最小项有2 n 项,上页,下页,返回,第1章,翻页,设一个三输入变量
20、的偶数判别电路，输入变量为A，B，C，输出变量为F。当输入变量中有偶数个1时，F=1；有奇数个1时，F=0。试用不同的逻辑函数表示法来表示。,例1.3.1,三个输入变量的最小项有 23=8个，即有8 个组合状态，将这 8 个组合状态的输入，输出变量都列出来，就构成了逻辑状态表，如表所示。,上页,下页,返回,第1章,把逻辑状态表中的输入，输出变量写成与或形式的逻辑表达式，将F=1的各状态表示成全部输入变量的与函数，并将总输出表示成这些与项的或函数，即逻辑表达式：,F=A B C+A B C+A B C+A B C,翻页,(2)逻辑表达式,上页,下页,返回,第1章,若将逻辑表达式中的逻辑运算关系用
21、相应的图形符号和连线表示，则构成逻辑图。,若将逻辑状态表按一定规则行列式化则构成图下图所示。,(卡诺图内容见 节）,翻页,(3)逻辑图,(4)卡诺图,逻辑函数的化简通常有以下两种方法：,1.应用运算法则化简,*2.应用卡诺图化简,1.3.2 逻辑函数的化简法,上页,下页,第1章,返回,翻页,1.应用运算法则化简,上页,下页,第1章,返回,翻页,解：Y=AB(1+C+D+E),上页,下页,第1章,返回,翻页,*2.卡诺图的表示及其化简,任何一个逻辑函数都可以表示为若干最小项之和的形式,二到五变量最小项的卡诺图,二变量卡诺图,三变量卡诺图,四变量卡诺图,五变量卡诺图,第1章,上页,下页,返回,翻页,化简步骤：,将函数化为最小项之和的形式,画出表示该逻辑函数的卡诺图,找出可以合并的最小项,选取化简后的乘积项,选取原则是：,这些乘积项应包含函数式中所有的最小项,所用的乘积项数目最少,每个乘积项包含的因子最少,第1章,上页,下页,返回,翻页,解：画出函数Y的卡诺图,即 m4 m6 为 1,1,找出合并最小项,1,选取化简乘积项,注意：找出合并最小项的方案会 有多种,第1章,上页,返回,下页,本节结束,例题1.3.4,
