SAT问题的NPC证明.ppt

可满足性问题的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 0 1 2 1 2 3 4 5 3 4 5 6 7 有限状态控制器 猜想模块 猜想头 读写头 证明思路总览 如何证明所有NP类问题SAT NP类问题的计算过程均可抽象为一个NDTM上的运作过程 因此 SAT的NPC证明等价于证明NDTMSAT 0 1 2 1 2 3 4 5 3 4 5 6 7 有限状态控制器 猜想模块 猜想头 读写头 证明思路总览 如何证明NDTMSAT 只要找到多项式变换f 设一个NP类问题所对应语言的一个字符串为x 若x被NDTM接受 则对应SAT问题的例子f x 回答为 是 任意的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的运转规则 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 有限状态控制器 猜想模块 猜想头 读写头 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项 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 用或逻辑式表达运转规则 或逻辑式中的布尔变量 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 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步 用或逻辑式表达运转规则 2 在每一时刻 M处于且仅处于一个状态 0 1 2 1 2 3 4 5 3 n 有限状态控制器 读写头 n 1 b b b ABm0 第i步 卡诺图 用或逻辑式表达运转规则 3 在每一时刻 读写头仅瞄准一个带格 0 1 2 1 2 3 4 5 3 n 有限状态控制器 猜想模块 猜想头 读写头 n 1 b b b 用或逻辑式表达运转规则 最多在步内判定一个猜想 而表示还要多读一个空白符 从而M知道结束了 3 在每一时刻 读写头仅瞄准一个带格 0 1 2 1 2 3 4 5 j n 有限状态控制器 读写头 n 1 b b b ABm0 第i步 卡诺图 用或逻辑式表达运转规则 4 在每一时刻 每个带格恰好写有一个带符 0 1 2 1 2 3 4 5 3 j n 有限状态控制器 猜想模块 猜想头 读写头 n 1 b b b 肯定有0 s中的一个字符 第i步 用或逻辑式表达运转规则 4 在每一时刻 每个带格恰好写有一个带符 0 1 2 1 2 3 4 5 3 j n 有限状态控制器 读写头 n 1 b b b 第i步 ABm0 卡诺图 用或逻辑式表达运转规则 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步计算过程的或逻辑式 读写头指向的带格 字符才有可能改变 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 读写头没指向的带格 字符不可能改变 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 合并两卡诺图 ABm0 卡诺图 ABm0 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 合并两卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 书错了 我看了Cook71年原文 没有这个式子 关于 6 的式子 他仅举一例 一笔带过 只告诉大家有这个东西而已 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 两式相与 代入无误 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 合并四个卡诺图得 书上代入出错 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 或逻辑式推导 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 或逻辑式推导 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 合并四个卡诺图得 现在代入所有的取值都对 Cook71中和书上的式子一致 可能是他的笔误 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 合并四个卡诺图得 书上代入出错 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 全过程只有状态和第j个带格上字符串可能变化 ABm0 卡诺图 用或逻辑式表达运转规则 6 第i步到第i 1步计算过程的或逻辑式 合并四个卡诺图得 书上代入出错 NDTM到SAT问题的多项式变换 以上6组逻辑式集合的并 即为一个SAT问题的句子集 显然可以在多项式时间内得到该SAT问题 而且若NP类问题的例子回答为 是 则对应的字符串x可被M接受 则对应的SAT问题有解 这就建立了一个NP类问题到SAT问题的多项式时间变换 从而问题得到证明 第一章数字逻辑基础 1 1数制和BCD码 1 2逻辑代数 1 3逻辑函数的表示和化简 返回 第1章 上页 下页 数字电路电路的特点 1 所处理的数字信号只有两种取值 1 0 2 电路抗干扰能力强 3 信息便于长期存储 便于计算机处理 概述 上页 下页 返回 第1章 翻页 逻辑代数运算规则 逻辑代数又称布尔代数 是分析与设计逻辑电路的工具 逻辑代数表示的是逻辑关系 它的变量取值只有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 CA B C A B C 上页 下页 反演定理 翻页 分配律 A B C A B A CA B C A B A C 返回 第1章 上页 下页 第1章 本节结束 返回 1 3逻辑函数的表示和化简 1 3 1逻辑函数的表示方法 1 3 2逻辑函数的化简法 上页 下页 第1章 返回 第1章 上页 下页 1 3 1逻辑函数的表示方法 返回 翻页 逻辑式 用基本运算符号列出输入 输出变量间的逻辑代数式 逻辑状态表 列出输入 输出变量的所有逻辑状态 卡诺图 与变量的最小项对应的按一定规则排列的方格图 最小项是指所有输入变量各种组合的乘积项 输入变量包括原变量和反变量 例如 二变量A B的最小项有四项 AB AB AB AB 三变量的最小项有八项 依此类推 n变量的最小项有2n项 上页 下页 返回 第1章 翻页 设一个三输入变量的偶数判别电路 输入变量为A B C 输出变量为F 当输入变量中有偶数个1时 F 1 有奇数个1时 F 0 试用不同的逻辑函数表示法来表示 例1 3 1 三个输入变量的最小项有23 8个 即有8个组合状态 将这8个组合状态的输入 输出变量都列出来 就构成了逻辑状态表 如表所示 上页 下页 返回 第1章 把逻辑状态表中的输入 输出变量写成与 或形式的逻辑表达式 将F 1的各状态表示成全部输入变量的与函数 并将总输出表示成这些与项的或函数 即逻辑表达式 F ABC ABC ABC ABC 翻页 2 逻辑表达式 上页 下页 返回 第1章 若将逻辑表达式中的逻辑运算关系用相应的图形符号和连线表示 则构成逻辑图 若将逻辑状态表按一定规则行列式化则构成图下图所示 卡诺图内容见4 2 2节 翻页 3 逻辑图 4 卡诺图 逻辑函数的化简通常有以下两种方法 1 应用运算法则化简 2 应用卡诺图化简 1 3 2逻辑函数的化简法 上页 下页 第1章 返回 翻页 1 应用运算法则化简 上页 下页 第1章 返回 翻页 解 Y AB 1 C D E 上页 下页 第1章 返回 翻页 2 卡诺图的表示及其化