SAT问题的NPC证明.ppt

1、可满足性问题的可满足性问题的NPC证明证明-Cook定理内容提要内容提要1.证明思路总览2.证明中用到的知识2.1非确定图灵机2.2非确定图灵机的运转规则3.证明的详细过程3.1用或逻辑式表达运转规则3.2建立NP类问题到可满足性问题的多项式变换4.可能用到的知识附录证明思路总览证明思路总览根据NPC问题定义来证明只要所有NPC问题均可在多项式时间内变换到SAT问题即可证明SAT问题为NPC.任意的NP类问题SAT问题证明思路总览证明思路总览如何证明所有NP类问题SAT?然而，若将每个NP类问题都多项式变换到SAT问题是不现实的，所以要抽取NP类问题的共性，建立NP类问题的统一计算模型-非确定

2、的图灵机（NDTM）.01 2-1-2-3-4-534 567.有限状态控制器猜想模块猜想头读写头证明思路总览证明思路总览如何证明所有NP类问题SAT?NP类问题的计算过程均可抽象为一个NDTM上的运作过程.因此，SAT的NPC证明等价于证明NDTMSAT.01 2-1-2-3-4-534 567.有限状态控制器猜想模块猜想头读写头证明思路总览证明思路总览如何证明NDTMSAT?只要找到多项式变换f；设一个NP类问题所对应语言的一个字符串为x，若x被NDTM接受，则对应SAT问题的例子f(x)回答为“是”。任意的NP类问题SAT问题证明思路总览证明思路总览现整理证明的思路如下：任意NP类问题0

3、1 2-1-2-3-4-534 567.有限状态控制器猜想模块猜想头读写头语言问题例子字符串对应作为输入建立图灵机的运作规则到SAT的多项式时间变换问题得证NP问题的统一模型问题的统一模型非确定图灵机计算模型01 2-1-2-3-4-534 567.有限状态控制器猜想模块猜想头读写头NDTM的运转规则的运转规则非确定图灵机计算过程与DTM不同（两阶段）：猜想阶段检验阶段NDTM的运转规则的运转规则01 2-1-2-3-4-534 567.有限状态控制器猜想模块猜想头读写头agcdBBBBBBBB初始输入字符串x写入图灵机猜想模块起作用，有限状态控制模块不起作用，从-1向左依次写入字符表中的任意

4、多个任意字符猜想阶段：ggg检验阶段：猜想模块不起作用，有限状态模块起作用NDTM的运转规则的运转规则NDTM的运转规则被总结为6项：（1）初始时刻，M处于初态，读写头瞄准带格，x放置在到的带格中；而，,皆为空白。0 12-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头n+1bbbNDTM的运转规则的运转规则NDTM的运转规则被总结为6项：（2）在每一时刻，M处于且仅处于一个状态。0 12-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头n+1bbbNDTM的运转规则的运转规则NDTM的运转规则被总结为6项：（3）在每一时刻，读写头仅瞄准一个带格。0 12-1-2-3

5、4-53.n.有限状态控制器猜想模块猜想头读写头n+1bbbNDTM的运转规则的运转规则NDTM的运转规则被总结为6项：（4）在每一时刻，每个带格恰好写有一个带符。0 12-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头n+1bbbNDTM的运转规则的运转规则NDTM的运转规则被总结为6项：（5）在最后一步，若x被M接受，则当时状态为。0 12-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头n+1bbbNDTM的运转规则的运转规则NDTM的运转规则被总结为6项：（6）M中一步计算的过程如下：xyxzypyq用或逻辑式表达运转规则用或逻辑式表达运转规则或逻辑式中的布

6、尔变量：(1)和状态相关的布尔变量：0 12-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头n+1bbb第i步用或逻辑式表达运转规则用或逻辑式表达运转规则或逻辑式中的布尔变量：(2)和读写头（Head）、带格相关的布尔变量：0 12-1-2-3-4-53.j.n.有限状态控制器猜想模块猜想头读写头n+1bbb第i步用或逻辑式表达运转规则用或逻辑式表达运转规则或逻辑式中的布尔变量：(3)和带格、带中字符相关的布尔变量：0 12-1-2-3-4-53.j.n.有限状态控制器猜想模块猜想头读写头n+1bbb第i步j(1)初始时刻的或逻辑式：0 12-1-2-3-4-53.n.有限状态控

7、制器猜想模块猜想头读写头n+1bbb用或逻辑式表达运转规则用或逻辑式表达运转规则第0步(2)在每一时刻，M处于且仅处于一个状态：0 12-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头n+1bbb肯定处于一个状态第i步用或逻辑式表达运转规则用或逻辑式表达运转规则(2)在每一时刻，M处于且仅处于一个状态：0 12-1-2-3-4-53.n.有限状态控制器读写头n+1bbbA B m0 0 0 m0 m3 m2 m1 第i步卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(3)在每一时刻，读写头仅瞄准一个带格：0 12-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头n

8、1bbb用或逻辑式表达运转规则用或逻辑式表达运转规则最多在 步内判定一个猜想，而 表示还要多读一个空白符，从而M知道结束了(3)在每一时刻，读写头仅瞄准一个带格：0 12-1-2-3-4-5j.n.有限状态控制器读写头n+1bbbA B m0 0 0 m0 m3 m2 m1 第i步卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(4)在每一时刻，每个带格恰好写有一个带符:0 12-1-2-3-4-53.j.n.有限状态控制器猜想模块猜想头读写头n+1bbb肯定有0s中的一个字符第i步用或逻辑式表达运转规则用或逻辑式表达运转规则(4)在每一时刻，每个带格恰好写有一个带符:0 12-1-2-3

9、4-53.j.n.有限状态控制器读写头n+1bbb第i步A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(5)在最后一步，若x被M接受，则当时状态为:0 12-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头n+1bbb第 步用或逻辑式表达运转规则用或逻辑式表达运转规则(5)在最后一步，若x被M接受，则当时状态为:0 12-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头n+1bbb第 步用或逻辑式表达运转规则用或逻辑式表达运转规则用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:读

10、写头指向的带格，字符才有可能改变A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:读写头没指向的带格，字符不可能改变A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:合并两卡诺图A B m0 0 0 m0 m3 m2 m1 卡诺图A B m0 0 0 m0 m3 m2 m1 0 01 10101111110100000用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:合并两卡诺图

11、0 01 10101111110100000用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:书错了？！我看了Cook71年原文，没有这个式子，关于(6)的式子，他仅举一例，一笔带过，只告诉大家有这个东西而已。用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式：0 01 10101111110100000用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:两式相与，代入无误用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格

12、上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2

13、 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:合并四个卡诺图得00 01 11 100000010111111010书上代入出错？！用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:或逻辑式推导用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:或逻辑式推导用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:合并四个卡诺图得00 01 11 100000010111111010现在代入所有的取值都对Cook71中和书上的式子一致，

14、可能是他的笔误用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转

15、规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:合并四个卡诺图得00 01 11 100000010111111010书上代入出错？！用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态

16、和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则(6)第i步到第i+1步计算过程的或逻辑式:合并四个卡诺图得00 01 11 10000001011111101

17、0书上代入出错？！NDTM到到SAT问题的多项式变换问题的多项式变换以上6组逻辑式集合的并，即为一个SAT问题的句子集。显然可以在多项式时间内得到该SAT问题，而且若NP类问题的例子回答为”是”，则对应的字符串x可被M接受，则对应的SAT问题有解。这就建立了一个NP类问题到SAT问题的多项式时间变换。从而问题得到证明；第一章第一章第一章第一章 数字逻辑基础数字逻辑基础数字逻辑基础数字逻辑基础1.1 1.1 数制和数制和BCDBCD码码1.2 1.2 逻辑代数逻辑代数1.3 1.3 逻辑函数的表示和化简逻辑函数的表示和化简返回第1章上页下页数字电路数字电路电路的特点电路的特点：1.1.所处理的数

18、字信号只有两种取值所处理的数字信号只有两种取值(1 1、0 0）；）；2.2.电路抗干扰能力强；电路抗干扰能力强；3.3.信息便于长期存储，便于计算机处理。信息便于长期存储，便于计算机处理。数字电路数字电路数字电路数字电路 组合逻辑电路：门组成组合逻辑电路：门组成 时序逻辑电路：触发器组成时序逻辑电路：触发器组成集成电路集成电路数字集成电路数字集成电路模拟集成电路模拟集成电路概述：概述：概述：概述：上页下页返回第1章 逻辑代数运算规则逻辑代数运算规则 逻辑代数又称布尔代数，是分析与设计逻辑代数又称布尔代数，是分析与设计逻辑电路的工具。逻辑代数表示的是逻辑关逻辑电路的工具。逻辑代数表示的是逻辑关

19、系，它的变量取值只有系，它的变量取值只有1 1和和0 0，表示两个相反，表示两个相反的逻辑关系。的逻辑关系。第1章上页下页 基本运算有：基本运算有：乘（与）运算、加（或）乘（与）运算、加（或）运算、求反（非）运算。运算、求反（非）运算。返回1.2 1.2 1.2 1.2 逻辑代数逻辑代数逻辑代数逻辑代数“与与”门门ABFF=A B“与非与非”门门FABF=A B“或非或非”门门ABF11F=A+B“或或”门门AB11FF=A+B“非非”门门1 1FAF=A名称图形符号逻辑表达式功能说明功能说明输入全输入全1 1，输出为，输出为1 1输入有输入有0 0，输出为，输出为0 0输入有输入有1 1，输

20、出为，输出为1 1输入全输入全0 0，输出为，输出为0 0输入为输入为1 1，输出为，输出为0 0输入为输入为0 0，输出为，输出为1 1输入全输入全1 1，输出为，输出为0 0输入有输入有0 0，输出为，输出为1 1输入有输入有1 1，输出为，输出为0 0输入全输入全0 0，输出为，输出为1 1基本逻辑关系基本逻辑关系上页下页第1章返回1.1.基本运算规则基本运算规则 A A=0 ,A A=A ,A=A上页下页第1章A+0=A ,A+1=1 ,A 0=0A 1=A ,A+A=1,A+A=A返回2.2.逻辑代数的基本定律逻辑代数的基本定律交换律：交换律：A+B=B+A ,A B=B A结合律：

21、结合律：A+(B+C)=(A+B)+C A (B C)=(A B)C上页下页 A B=A+B，A+B=A B吸收定律：吸收定律：A+AB=A+B ,A+AB=A反演定理：反演定理：分配律：分配律：A(B+C)=A B+A C A+B C=(A+B)(A+C)返回第1章上页下页第1章例题例题1.2.1 证明证明 AB+AC+BC=AB+AC解：解：AB+AC+BC=AB+AC+(A+A)BC =AB+AC+ABC+ABC=AB+ABC+AC+ABC=AB(1+C)+A(C+BC)=AB+AC返回1.31.3 逻辑函数的表示和化逻辑函数的表示和化逻辑函数的表示和化逻辑函数的表示和化简简简简1.3.

22、11.3.1 逻辑函数的表示方法逻辑函数的表示方法逻辑函数的表示方法逻辑函数的表示方法1.3.2 1.3.2 逻辑函数的化简法逻辑函数的化简法逻辑函数的化简法逻辑函数的化简法上页下页第1章返回第1章上页下页1.3.11.3.1 逻辑函数的表示方法逻辑函数的表示方法返回 逻辑式：逻辑式：用基本运算符号列出输入、输出变量间 的逻辑代数式 逻辑状态表逻辑状态表：列出输入、输出变量的所有逻辑状态 卡诺图：卡诺图：与变量的最小项对应的按一定规则排列 的方格图 用逻辑符号表示输入、输出变量间的逻辑关系 逻辑图：逻辑图：最小项是指所有输入变量各种组合的乘积项，输入变量最小项是指所有输入变量各种组合的乘积项，

23、输入变量包括原变量和反变量。例如，二变量包括原变量和反变量。例如，二变量A，B B的最小项有四项：的最小项有四项：AB，AB,AB,AB;三变量的最小项有八项三变量的最小项有八项;依此类推，依此类推，n 变变量的最小项有量的最小项有2 2 n n 项项上页下页返回第1章设一个三输入变量的偶数判别电路，输入变量为A，B，C，输出变量为F。当输入变量中有偶数个1时，F=1；有奇数个1时，F=0。试用不同的逻辑函数表示法来表示。例例1.3.1输 入输 出A B CF 0 0 0 10 0 0 1 0 0 0 0 1 1 0 00 1 0 00 1 0 00 0 1 1 1 1 1 11 0 0 01

24、 0 0 01 0 1 1 0 1 1 11 1 01 1 0 1 11 1 1 1 1 1 0 0 三个输入变量的最小项有23=8个，即有8个组合状态，将这8个组合状态的输入，输出变量都列出来，就构成了逻辑状态表，如表所示。解：解：(1)逻辑状态表逻辑状态表上页下页返回第1章 把逻辑状态表中的输入，输出变量写成与或形式的逻辑表达式，将F=1的各状态表示成全部输入变量的与函数，并将总输出表示成这些与项的或函数，即逻辑表达式：F=A B C+A B C+A B C+A B C输 入输 出A B CF 0 0 0 10 0 0 1 0 0 1 0 0 1 0 00 1 0 0 1 0 0 00 1

25、 1 0 1 1 1 11 0 0 1 0 0 0 01 0 1 1 0 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 0 0(2)逻辑表达式逻辑表达式上页下页返回第1章 若将逻辑表达式中的逻辑运算关系用相应的图形符号和连线表示，则构成逻辑图。ABCABCA BCF111&1若将逻辑状态表按一定规则行列式化则构成图下图所示。ABC0 01 10101111110100000 1 1 0 0 1 0 1 1 0(卡诺图内容见4.2.2节）(3)逻辑图逻辑图(4)卡诺图卡诺图 逻辑函数的化简通常有以下两种方法：1.应用运算法则化简*2.应用卡诺图化简1.3.2 1.3.2 1.3

26、2 1.3.2 逻辑函数的化简法逻辑函数的化简法逻辑函数的化简法逻辑函数的化简法上页下页第1章返回1.1.应用运算法则化简应用运算法则化简化简逻辑式子应用较多的公式：A+1=1 ,AA=0 A+A=1,A+A=A A A=A ,A=A A B=A+BA+B=A BA+AB=A上页下页第1章返回解解：Y=AB(1+C+D+E)=AB=(AB+A)+B=A+B利用利用A+1 1=1 1运算法则运算法则！解解：Y=AB+A B=AB+A+B利用利用AB=A+B 运算法则运算法则！利用利用A+AB=A 运算法则运算法则！上页下页第1章返回化简化简 Y=AB+ABC+AB(D+E)例题例题1.3.21

27、3.2化简化简Y=AB A B 例题例题1.3.31.3.3*2.2.卡诺图的表示及其化简卡诺图的表示及其化简任何一个逻辑函数都可以表示为若干最小项之和的形式二到五变量最小项的卡诺图A B m0 1 10 01 10 0 ABA B m0 A B m3 A B m2 A B m1 ABC0 01 10101111110100000m0m1m4m5m2m6m3m7二变量卡诺图三变量卡诺图m0m1m2m4m5m6m8m9m10m11m15m7m3m12m13m14ABCD00 01 11 100000010111111010四变量卡诺图m2m24CDEABm0m1m3m6m7m5m4m8m9m1

28、1m10m2m14m15m13m12m25m26m27m30m31m29m28m16m24m17m19m18m22m23m21m20五变量卡诺图第1章上页下页 卡诺图的表示：卡诺图的表示：返回化简步骤：将函数化为最小项之和的形式 画出表示该逻辑函数的卡诺图 找出可以合并的最小项 选取化简后的乘积项选取原则是：这些乘积项应包含函数式中所有的最小项 所用的乘积项数目最少 每个乘积项包含的因子最少第1章上页下页返回 卡诺图化简卡诺图化简 解：画出函数Y的卡诺图BCA00 01 11 1001对应AC项：因为AC=A（B+B）C =A B C+A B C所填入项应是A B C A B C即m4m6为11 11 1对应A C项：m1m3为11 11 1对应B C项：m2m6为11 1对应B C项：m1m5为10 00 0找出合并最小项1 1选取化简乘积项ACBCABY=AC+BC+AB注意：找出合并最小项的方案会注意：找出合并最小项的方案会 有多种有多种第1章上页返回下页 用卡诺图化简法将下式化简为最简与用卡诺图化简法将下式化简为最简与 或函数式或函数式 Y=AC+AC+BC+BC 例题例题1.3.41.3.4