计算的复杂性第七章NP完全问题.ppt

Email guxf 2020年3月25日星期三 计算的复杂性 计算机科学与工程学院 顾小丰 99 2 2020 3 25 第7章NP完全问题 判定问题 语言和编码多项式变换与可满足性问题非确定型图灵机NP类 NP完全问题与Cook定理强NP完全问题Co NP类问题NP困难问题空间复杂性简介 99 3 2020 3 25 序 对一个已确定是可计算的问题 人们总试图寻求实现它的最优算法 然而对有些问题 这个工作难度很大 目前还不能做到这点 目前人们已经证明了一些问题 它们的时间复杂性是多项式阶的 这只须设计一个实现它的时间复杂性是多项式阶的算法即可 例如分类 又称排序 问题 这样一类问题将被称之为P类问题 还有一类问题 人们已经设计出实现它的时间复杂性为指数阶的算法 并且已证明该问题不存在多项式阶的算法 例如梵塔问题 这样一类问题人们称之为顽型问题 但是有这样一类问题 人们目前已设计的实现它的算法其时间复杂性为指数阶的 但还不能肯定它有或没有多项式阶的算法 例如第6章讨论的当m 2时任意图的m 可着色问题 为研究这类问题 人们又设计一种称为非确定图灵机的计算模型 这些问题对应一个非确定的图灵机 而且可以在多项式时间内完成计算 人们称这类问题为NP问题 NP是NondeterministicPolynomial的缩写 即非确定的多项式的意思 99 4 2020 3 25 1971年S Cook发表了 TheComplexityofTheoremProvingProcedures 这篇著名论文 1972年R Karp发表了 ReducibiltyAmongCombinatorialProb1ems 从此奠定了NP完全理论的基础 NP完全理论指出在NP类中有一些问题具有以下性质 若其中一个问题获得多项式算法 则这一类问题就全部获得了多项式算法 反之 若能证明其中一个问题是多项式时间内不可解的 则这 类问题就全部是多项式时间内不可解的 这类问题将称之为NP完全问题 NP完全理论不打算找出这一类问题的算法 仅仅着眼于证明这一类问题的等价性 即证明它们的难度相当 NP完全理论还很年轻 有许多问题等待人们研究 例如 NP P 还是相反 P是NP的真子集 这个问题是当代计算机科学中的一大难题 99 5 2020 3 25 7 1判定问题 语言和编码 我们讨论的几种计算模型 都可以认为是语言的接受器或函数的计算器 为讨论问题简明 本章只讨论语言的识别问题 这是因为象图论 数论 逻辑和规划中的种种问题常常可以表示为语言的识别问题 其它的计算问题往往都有对应的判定问题 这种问题只有两个可能的解 或者回答 是 或者回答 否 99 6 2020 3 25 判定问题 定义7 1判定问题 是由实数集合D 和 是 的实例子集Y D 组成 但是 我们感兴趣的多数判定问题具有相当数量的附加结构 在描述判定问题时 要强调这些附加结构 我们用来规定问题的标准格式由两部分组成 第一部分用各种分量 如集合 图 函数 数字等规定该问题的一般实例 第二部分陈述根据这个一般实例提出的是 否问题 规定D 和Y 的方法是明显的 一个实例属于D 当且仅当它可以通过用规定类型的具体对象替换一般实例中的所有分量得到 而这个实例属于Y 当且仅当具体到这个实例时 对所陈述的问题的回答为 是 99 7 2020 3 25 货郎担问题 实例 一个有穷的 城市 集合C c1 c2 cm 对于每一对城市ci cj C有 距离 d ci cj Z 以及界限B Z 这里Z 表示正整数集合 问 是否有经过C中所有城市的 旅行路线 其全长不超过B 即是否有C的一个排列次序使得 99 8 2020 3 25 语言 我们只考虑判定问题的原因是因为它们有一个非常自然的 适合在数学上精确的计算理论中研究的形式对应物 这个对应物叫做 语言 其定义如下 定义7 2对于任意有穷符号集合 我们用 表示所有 的有穷字符串组成的集合 如果L是 的一个子集 我们称L是字母表 上的语言 例如 如果 0 1 那么 由空字符串 字符串0 1 00 01 10 11 000 001以及所有其它0和1的有穷字符串组成 于是 01 001 111 1101010 是 0 1 上的一个语言 由所有完全平方数的二进制表示组成的集合以及集合 0 1 本身也都是 0 1 上的语言 99 9 2020 3 25 编码 判定问题的每一实例可以编码成一个符号串 这样就将判定问题重新描述为一个语言的识别问题 这个语言必须由对应的判定问题中回答 是 的一切实例编码的串组成 在选择编码方法时 必须慎重 因为一个问题的复杂性可能与编码的方法有关 由于问题的难度在本质上不依赖于用来决定时间复杂性的具体编码方法和计算机模型 因此很难想象一个 合理的 编码方法与标准的编码方法之间的差异超过多项式 99 10 2020 3 25 编码的条件 实例I的编码必须是简洁的 不能 填塞 不必要的信息或符号 I中出现的数字必须用十进制 或二进制 八进制 以及以任何不等于1的数为基的进制 表示 虽然不可能把我们在这里用 合理的 这个词表示的含义形式化 但是下述两个条件抓住了这个概念的主要内容 99 11 2020 3 25 编码的标准 如果我们规定只使用满足这些条件的编码方法 那么具体使用什么编码方法将不会影响关于一个给定问题的难度的判断 为此 我们对问题的标准表示约定如下 整数用十进制表示 用十进制数1 2 n表示一个图的n个节点 用 i1 i2 表示图中的边 其中i1 i2分别是该边的两个端点 具有n个命题变元的布尔表达式由 与 或 非 与整数1 2 n 命题变元 所组成的字符串表示 其中 可以省略 但不引起混淆 必要时可以加括号 例如 布尔表达式 P1 P2 P3可以写成 1 2 3 99 12 2020 3 25 当把整数及其它符号都采用二进制编码后 一个问题的判定过程就可以形式地描述如下 已知L 0 1 对于x 0 1 若x L则回答 是 若x L 则回答 非 这里 0 1 是指由有限个0和1组成的串的集合 再次重申 我们的讨论仅限于语言的识别 99 13 2020 3 25 7 2多项式变换与可满足性问题 定义7 3P L 0 1 L为确定图灵机在多项式时间内所接受 该怎义中符号 意义为 定义为 定义7 4 f f 0 1 0 1 且f可在多项式时间内完成 这个定义是说 表示可在多项式时间内完成 0 1 0 1 这一转换的集合 99 14 2020 3 25 多项式变换 定义7 5若A 0 1 B 0 1 且存在f 使得x A f x B成立 则称A可多项式变换于B 记作 或简称A变换为B 符号的意思是 存在一台确定图灵机M 它将可以A在多项式时间内转换为B 99 15 2020 3 25 引理7 1 引理7 1若 B P 则A P 证明 x A f x Bf 所以由f产生的输出也必有多项式界 设为多项式g 但B也有多项式界 设为h 对于输入x 先作用以f 接着解属于B的问题 总共所需时间 g x h g x 显然也是多项式 所以A P 这个过程可以用下图表示 问题A的输入x 问题B的输入 最长为 g x f转换至多在g x 内将x换成f x 多项式h g x 内求解B 输出问题B的解 99 16 2020 3 25 可满足性问题 实例 集合L A B A B c1 c2 ck是L的有限子集 称为子句 每个ci中不出现L中的互补对 即x cI则 x ci i 1 2 k 问 是否存在一集合S L 满足以下两个条件 s中不包含互补对 99 17 2020 3 25 从数理逻辑看来 设U u1 u2 um 是一个布尔变量集合 关于U的真值赋值是一个函数t U T F 如果t u T 我们称u在t下取 真值 如果t u F 我们称u取 假值 如果u是U中的一个变量 那么u和 u是U上的文字 文字u在t下取真值当且仅当变量u在t下取真值 文字 u取真值当且仅当变量u取假值 U上的子句是U上的一个文字集合 例如 u1 u2 u8 它表示这些文字的析取 对于U上的一个真值赋值 这个真值赋值满足它当且仅当它至少有一个元素在这个赋值下取真值 除去t u1 F t u2 T和t u8 F之外 t满足上面那个子句 U上的子句类C是可满足的当且仅当存在关于U的一个真值赋值同时满足C中所有子句 我们称这样一个真值赋值是满足C的真值赋值 99 18 2020 3 25 命题逻辑的可满足性问题 实例 布尔变量集合U以及U上的子句类C 问 是否存在满足C的真值赋值 例如 U u1 u2 和C u1 u2 u1 u2 是SAT的一个实例 对这个实例的回答为 是 t u1 t u2 T给出一个满足的真值赋值 如果用C u1 u2 u1 u2 u1 代替C也给出一个实例 对这个实例的回答为 否 C 不是可满足的 可满足性问题常用符号SAT表示 它是Satisfiability的缩写 99 19 2020 3 25 图的m 可着色问题 实例 无向连通图G V E 和m种不同的颜色 用这些颜色为G的各节点着色 每个节点着一色 问 是否有使得G中任何一条边的两个节点的颜色不同的着色法 例7 1图的m 可着色问题可以多项式变换为SAT 证明 已知图G的节点数为n c1 c2 cm表示m种颜色 设 99 20 2020 3 25 因此 G的每一种着色方案对应于给mn个变量 Pij 的一种赋值 但是必须满足条件 1 每个节点至少有一种颜色 故对任一i 有子句Pi1 Pi2 Pim 2 相邻的节点着不同颜色 故对图G的任意一对相邻节点 r s 必有 Prj Psj 1 j m 于是图G可m 着色的充要条件是可对变量Pij赋值i 1 2 n j 1 2 m 使得由 1 和 2 构成的所有子句取值为T 转换步骤 1 2 所需的时间有多项式的界 99 21 2020 3 25 哈密顿回路问题 HC 实例 图G V E 问 G是否包含一条哈密顿回路 即是否有G的节点排列次序使得 vn v1 E和 vI vi 1 E 1 i n 这里n V 例7 2哈密顿回路问题 HC 可以多项式变换为货郎担问题 TS 证明 函数f的定义十分简单 设G 为给定的HC的实例 V n 对应的TS的实例有一个等于V的城市集合C 对任意两个城市i j 若 i j E 则规定d i j 1 否则d i j 2 令界限B V 99 22 2020 3 25 容易 非形式地 看到 能够用一个多项式时间算法计算这个函数f 对于个规定的耗费d i j 只需要检查 i j 是否是G中的一条边 所以f 假设 1 2 n 是G中的一条哈密顿回路 那么 1 2 n 也是f G 中的一条周游路线 并且这条周游路线的耗费为B n 这是因为在这条周游路线中经过的城市之间每一段耗费对应G中一条边 从而耗费为1 反之 假设 1 2 n 是f G 中的一条总耗费为不超过B的周游路线 因为任意两个城市之间的耗费不是1就是2 而在计算周游路线的总耗费时恰好是n个这样的耗费相加 所以根据B n 每一对相继访问的城市间的耗费恰好为1 由的f G 定义 得到 i i 1 1 i n和 n 1 都是G的边 从而 1 2 n 是G的一条哈密顿回路 99 23 2020 3 25 引理7 2 若L1L2 L2L3 则L1L3 99 24 2020 3 25 7 3非确定型图灵机 为讨论NP问题 再引进一种虚设的计算模型 即非确定型图灵机 定义7 6一个k 带非确定型图灵机 NDTM M可由下述7元组确定 M 其中Q T I b q0和qr的定义与确定型图灵机相同 参看第5章定义5 3 而 是 Q Tk A A Q T L R S k 99 25 2020 3 25 定义指出 非确定型图灵机 对于由一个状态与k个磁带符号所给定的序组 确定的下一动作不是唯一确定的 它将要在一个有穷集合A中选择 猜测 它在同一时刻里可以做多种运算 但要注意 一个NDTM机M只能在A中任意选择其下一个动作 然而不能选A以外的动作 假定 q a 1 d 1 a 2 d 2 a k d k q a1 a2 ak 并且非确定型图灵机M正处在状态q 且第i个磁头 1 i k 正扫描着第i条磁带上符号ai的某一方格 则机器的下一动作可以进入状态q 并把ai变为a i 而各磁头的动作由d i指定 99 26 2020 3 25 图灵机的格局 定义7 7称D 为k 带图灵机的一个格局 若每一个ai形为xqy 其中xy是在当前状态q下第i条带上的符号串 不计右端的空白符 q为机M的当前状态 q后面的第一个符号是M在第i条带的带头所扫描的方格符号 若机M是确定型的且当前格局D不处于停机状态 则可由下一动作函数 唯一地确定下一个格局D 并记为D MD 称为D转到D 对于非确定型机M 从当前格局D可导致多于一个的下一格局 但仅有穷个 若D 是其中之一 则记为D MD 或D D 若不引起混乱 若对某个k 1 有c1 c2 ck或cl ck 则可记作c1 ck 99 27 2020 3 25 非确定型图灵机的作用 非确定型图灵机M可以用作一种语言L的识别器 对于语言L 我们可以构造一台非确定型图灵机M 让机器的带符包括该语言的字母表 输入字母表 以及伪空白符b和其它一些特定符号 辅助符号 机器处于开始状态时 将输入w打印在第一条磁带的最左面部分上 此外全为空白 而其它的磁带此时全为空白 把各条磁带的磁头放在该磁带之最左一格上 称输入w被这台机器接受 仅当 其中a1 因此一切a2 ak 有停机状态qr于其中 99 28 2020 3 25 定义7 8对语言L 按上述方法构成的非确定型图灵机NDTM接受L 当且仅当对w L NDTM可接受w 对w L NDTM陷入不停机状态 非确定型图灵机NDTM接受语言L 记作L NDTM 非确定型图灵机NDTM接受语言L 99 29 2020 3 25 例7 3等分划问题 试设计一台NDTM 它接受了形如 的字 其中i1 i2 ik为非负整数满足下述要求 有I 1 2 k 使 换言之 字w被接受当且仅当用字w所表现的数列i1 i2 ik 可以被分割为两个子序列 各子序列的数之和相等 这个问题是所谓等分划问题 已经知道 它是一个NP完全问题 99 30 2020 3 25 下面设计一台三带NDTM来接受所述的语言 这台NDTM的工作情况是 对输入磁带从左到右进行扫描 每次搜索全为0的一个磁带段0ij 并且不确定地在第2或第3磁带上增补选ij个0 当扫描到输入末端时 机器便核对第2磁带与第3磁带上0的个数 若相等则接受 注意 可能有许多情况导向了不相等 但我们关心的是 有一种选择导致相等 设NDTM 下一动作函数 如表7 1所示 下面给该机器输入1010010 我们从许多可能选择的计算中 列出两个可能的计算 其中的第一个导向了对该输入是接受的 而第二个计算不接受该输入 因此 按我们的定义 该机器接受1010010 99 31 2020 3 25 表7 1例7 3中非确定型图灵机M的下移函数 99 32 2020 3 25 接受 停止 因无下一格局 99 33 2020 3 25 NDTM的时空复杂性 定义7 9称一台NDTM机M的时间复杂性是T n 假若对于任何长为n的可接受的输入w 都存在着一条导向接受指令的计算路 该计算路至多有T n 步 称M的空间复杂性是S n 假若对于上述输入w 有一条导向接受指令的计算路 于其中在每一条带上至多有S n 个相异的磁带方格被扫描过 99 34 2020 3 25 例7 3的复杂性 例7 4对于例7 3所设计的机器M 其时间复杂性为2n 2 而空间复杂性为n 1 对所述的空间复杂性是显然的 为了看出时间复杂性为2n 2 只须注意 当对输入扫描结束 共用n 1步 后 要回头对2 3磁带进行比较 不超过n 1步 99 35 2020 3 25 用DTM模拟NDTM 原则上 对于每一台NDTM机 都可以设计一台DTM机来模拟它 使得两者皆接受了同一语言 然而DTM的时间耗费要大得多 可以证明 这种模拟的时间耗费下界是指数型的 确切地说 设T n 是 时间可构造的 函数 即存在一台DTM机 给出该机的任一输入n 机器将在第T n 步停机 则对每一台为T n 时间囿界的NDTM机M 可以找到一个常数c l和一台DTM机M 使L M L M 且M 的时间复杂性为O cT n 为了证明这个结果 可以用穷举算法来构造一台模拟M的DTM机M 首先 可以找到常数d 使得NDTM机M在任何情况下的下一动作 99 36 2020 3 25 的选择可能不超过d个 因此机器M的长度不超过T n 的任何一条计算路都可用字母表 0 1 dn 1 的长不超过T n 的一个字来表现 这些字至多为 d 1 T n 个 事实上 只有dT n 个可将其按字母次序排列 对于长为n的输入x DTM机M 模拟NDTM如下 依次模拟上述w 为 w 即M 在这次模拟中的计算路 如M中不存在如w所示的计算路或者w不是M接受x的计算路 则M 去模拟w的下一个次序的字母所示的计算路 注意 M 在每次模拟时要耗时O T n 于是整个模拟至多耗费时间O T n d 1 T n 事实上为T n dT n 取c 2 d 1 即可 细节的叙述要用到T n 的时间可构造性 因模拟w到长为T n 止 这里就不再叙述了 这样我们就证了下述定理 99 37 2020 3 25 定理7 1 如果取上述非确定型图灵机类为计算模型 则这个计算模型同已知的种种计算模型等价 对于任一台NDTM时间囿界为T n 且T n 为时间可构造的机器M 都可以找到常数c 1和DTM机M 使L M L M 且M 的时间下限为O cT n 然而 我们不知道有一个为NDTM在时间复杂性T n 里接受的语言L 一切DTM在时间复杂度T n 都不能接受它 99 38 2020 3 25 定理7 2 若NDTM机M的空间复杂性为S n 且S n 使空间可构造的 则存在一台DTM机M 它的空间复杂性是O S3 n 且L M L M 所谓一个函数S n 是空间可构造的 如果存在一台DTM机M 当给它一个长度为n的输入 M机将在它的一条带的第S n 个方格上放置一个特殊的标记符号并且对任何带不会使用多于S n 个方格 绝大多数函数 例如多项式 2n n n1og n 1 都是空间可构造的 99 39 2020 3 25 定理7 3 设语言L可以为时间复杂性为T n 的k 带NDTM机所接受 则L也可以被一台时间复杂性为0 T2 n 的单带NDTM机所接受 这个定理使我们在讨论与非确定型图灵机有关问题时 可以只对单带机而言 于是便简单一些 99 40 2020 3 25 7 4NP类 有了非确定型图灵机这一计算模型 这里将讨论一个新的语言类NP类问题 定义7 10NP L 0 1 L为非确定图灵机在多项式时间内所接受 因为确定型图灵机是非确定型图灵机的特殊情况 于是有 P NP目前人们尚未证明P NP 或P是NP的真子集 99 41 2020 3 25 例7 5 无向图的团集问题属于NP类 团集问题定义如下 实例 图G V E 和正整数J v 问 G是否包含大小不小于J的团 即是否有子集V V 使得 V J并且V 中每两个节点都由E中的一条边连接着 99 42 2020 3 25 首先对团集问题编码 设G V E V 1 2 n 则表现团来问题的语言L由形如 k i1 j1 i2 j2 im jm 组成 这里k 2 ik jk V且 ik jk E k 1 2 m 如图7 4 1所示 当k 3 可编码为 3 1 2 1 4 2 3 2 4 3 4 3 5 4 5 当然可以用二进制编码 因为对于任意两种编码语言 可以在多项式时间内互相解释 如下设计工台NDTM机M 输入长为n的串w k i1 j1 i2 j2 im jm 99 43 2020 3 25 该机可在O n3 时间内认知w 其构成是 1 若k n 机M计算1步便停机在拒绝指令上 2 k n 机M在G的一切k点子集中猜测 选择 一个k点团集 并对之进行验证 确切地悦 就是要验证所有猜测的k点子图的任何两个相异点间均有一条边连接 注意到一个k点团集共有 条边 每验证一边可从头到尾看完字w 长度为n 故共用O n3 步 注意 这台NDTM的能力是它能同时 并行 地对一切可能的k点子图进行验证 若有k点团集存在 则接受w 否则拒绝 而时间复杂性仅为O n3 99 44 2020 3 25 例7 6 命题逻辑的可满足问题是一个NP问题 99 45 2020 3 25 首先把布尔式写成标准编码 例如 Pl P2 Ps写成 1 2 3 设L表示命题逻辑的可满足问题的语言 要证明L NP为此 可构造一台NDTM机M 其时间复杂性为O n2 且L M L 输入w的长为n A1 A2 Am 1 m n 其中每一Ai为a1 a2 ak 1 k n 而每一ai为j或j NDTM机M猜测 选择 一个满足指派 不超过2n种 只要有一个Ai 0 则拒绝w 当所有Ai 1 则接受w 而对每一个Ai Ai 0 一切aj 0 对每一Ai核对是否为0要用O n 步 于是核对是否w 0要用O n2 步 这里之所以在步可以接受或拒绝 使因为我们使用了对于一切指派 并行 地处理这一不确定的过程 99 46 2020 3 25 定理7 4 1 SAT 2 团集问题 3 节点覆盖问题 VC 4 哈密顿回路问题 HC 5 图的m 可着色问题 6 回路节点集问题 7 回路边集问题 8 有向图哈密顿回路问题 9 集合覆盖问题 10 恰当覆盖问题 下面各问题都在NP中 99 47 2020 3 25 实例 图G V E 和正整数k v 问 G是否有大小不超过k的节点覆盖 即是否有子集V使得 V k并且对每一条边 u v E u和v中至少有一个属于V 节点覆盖问题 VC 回路节点集问题 实例 有向图G V E 和正整数k v 问 G是否有元素个数为k的回路节点集 即是否有S V S k 使得G的每一条回路都有一个点在S中 99 48 2020 3 25 回路边集问题 实例 向图G V E 和正整数k E 问 G是否有元素个数为k的回路边集 即是否有F E F k 使得G的每一条回路都有一条边在F中 有向图哈密顿回路问题 实例 有向图G V E 问 G是否包含一条哈密顿回路 即是否有G的节点排列次序使得 E和 E 1 i n 这里n V 99 49 2020 3 25 集合覆盖问题 实例 一族 有穷 集合S1 S2 Sn及正整数k n 问 是否存在子族Si1 Si2 Sik使得 实例 一族 有穷 集合S1 S2 Sn及正整数m n 问 是否存在子族Si1 Si2 Sim使得 恰当覆盖问题 且Sij sim j m 99 50 2020 3 25 7 5NP完全问题与Cook定理 在NP类问题中 Cook首先发现可满足问题具有特殊的重要性质 之后人们又证明了有很多NP类中的问题 也具有同样的性质 于是形成了NP完全问题类 99 51 2020 3 25 NP完全的定义 定义7 11称L0 NP为NP 完全的 简称NPC 如果下述条件能满足 对于认识L0的时间复杂性为T n n的任一个确定算法 那么对每一个L NP都能找到一个时间复杂性为T PL n 的确定算法认识L 这里PL n 是依赖于L的一个确定多项式 上述定义有时称为广义NP完全的定义 在NP完全理论中常用以下另一种关于NP完全的定义 称为狭义NP完全 定义7 12称L0 NP是NP完全的 如果对一切L NP都有 99 52 2020 3 25 定理7 5 若L0是狭义NP完全的 则L0是广义NP完全的 证明 设L0为某一确定型图灵机A在时间T n n内所认识 不妨设T n 为递增的 因L0为狭义NP完全 于是存在确定型图灵机M 它可以把L NP在多项式P n 内将L翻译成L0 构成一台新机器M 如下 输入w L 先用M将w译成w0 L0 时间耗费界为P w 再将w0输入A并计算 时间花费界为T w0 因为M机输出w0时至少用过 w0 个磁带方格 故对应的计算步数不能少于 w0 于是 w0 P w 99 53 2020 3 25 总之 新机M 认识L的时间上界应满足 P w T w0 P w T P w 此步因为T n 是递增函数 再由T n n 可得 P w T P w 综上可得 P w T w0 2T P w T 2P w 即M 机可以在T PL n 内认识L 这里PL n 2P n 是与L有关的一个多项式 于是由定义7 11 L0是NP完全的 但是以上定理7 5之逆 至今还没有肯定或否定的证明 99 54 2020 3 25 定理7 6 我们以后谈到NP完全的 都是指定义7 5 2给出的狭义NP完全 由以上定理 当然也是广义NP完全的 由NP完全的问题的定义 显然有 定理7 6设L0为任一NP完全的语言 那么L0 P P NP这个定理恰说明NP完全理论的重要性 人们只须对具体某个NP完全的问题深入研究 如果能肯定它是P类 则所有NP问题就都属于P类 反之如果能肯定它不是P类 则NP类就是P类的真扩集 或说P类是NP类的真子集 NP完全的问题存在吗 Cook在1971年首先回答了这个问题 99 55 2020 3 25 证明 例7 6已证明了SAT NP 故只须证明对每一个语言L NP 换言之 对于一台在多项式界时间内接受L的NDTM机M 对M的一个输入w 都有一个 依赖于L的 多项式界的算法来构成一个布尔式w0 使得w0可满足当且仅当M接受w 由定理7 3 我们可假定M是单带的 假定M有状态q1 q2 qs 磁带符号x1 x2 xs M的时间复杂性为P n 若给机M输入长为n的w 如M接受w 则M在P n 步内接受停机 故至少存在一条计算路Q0 Ql Qg 这里Q0是开始格局 Qg为接受格局 g P n Cook定理 定理7 7命题逻辑的可满足问题是NP完全的 99 56 2020 3 25 我们的目的是构造一个布尔式w0 它能 模拟 机M中所能进入的格局序列 即w0的变元的每个真 1 假 0 指派表现了M的至多一条计算路 也可能所表现的不是M的合法的计算路 w0取值1当且仅当指派表现了导致接受格局的计算路Q0 Q1 Qg 换言之 w0可满足当且仅当M接受w 我们先叙述一下w0中要用到的命题交元 1 C取值1当且仅当机M在瞬时t即第t步的第i个磁带方格内有符号xj 其中1 i P n 这是因为机M的时间复杂性为P n 则磁带复杂性 P n 1 j m 0 t P n 2 s取值1当且仅当机M在瞬时t处于状态qk 这里1 k s 0 t P n 3 H取值1当且仅当在瞬时t磁头扫描着第i个磁带方格 这里1 i P n 0 t P n 99 57 2020 3 25 上述命题变元共有m P n 2 s P n P2 n 个 故阶为O P2 n 如果要用二进制数来编码表示这些命题变元 则至多用到Clog2n位的二进数即可 C为与P有关的常数 事实上 设P n 为P0次多项式 则O P2 n O n2P0 命C 2P0 1 则Clog2n位二进数可表示2Clog2n nC n2P0 1个十进制数 但我们下面仍用一个单独的符号表示一个命题变元 这样做将失去因子Clog2n 但这并不影响我们对问题的讨论 因为我们只需要一个多项式时间囿界的函数 我们要以上述命题变元来构成w0 在构造中要用到一个谓词U x1 x2 xr 它取值为1当x1 x2 xr中恰有一个取值为1 U可表示为 7 1 99 58 2020 3 25 这个式子中的第一个因子说xi中至少有一个取值1 其余的r r 1 2个因子说没有两个相异的xi同时取值为1 注意 U的长度是 r r 1 5r r 1 2即O r2 严格地说 因一个命题变元符号至多O Clogr 二进制码表示 故U的长度至多为O r3 若M接受w 则存在一个接受w的计算路Q0 Q1 Qg 为使讨论简单 可不失一般地假定 不管M是否已进入接受格局 我们都让M继续 计算 下去 但对于已进入接受格局时 其下面的 计算 将不移动磁头也不改变已进入的接受状态 直到第P n 个格局止 下面 可用7个式子A B G来构成w0 它判断了 Q0 Q1 Qg是一条接受w的计算路 这里每个Qi长为P n g P n 99 59 2020 3 25 判断Q0 Q1 QP n 为一条接受w的计算路等同于判断下述7条事实 1 在每个格局Qi中 磁头只扫描着一个磁带方格 2 每个格局Qi中的每一个磁带方格内只有一个磁带符号 3 每个格局Qi中只有一个状态 4 在该计算路中 从一格局到它的下一格局时 至多只能修改上一格局中被扫描方格内的符号 5 该计算路各格局的状态 磁头位置以及磁带方格内的符号的变化符合M的下一动作函数的要求 6 Q0是机M在输入w0时的开始格局 7 该计算路的最后一个格局的状态是停机状态 99 60 2020 3 25 现在来构成与判断 1 7 相应的布尔表达式A G 1 令At H H H At的意思是说 在瞬时t M的磁头恰好扫描着某一磁带方格 则置A A0A1 AP n 表述了上述判断 1 注意 因用一个符号表示一个命题交元H 故A的长为O P3 n 而且可在O P3 n 时间内 用一台DTM机 写下这个式子 2 令Bit C C C 它的意思是说 在瞬时t 第i个磁带方格内只有一个符号 则置 表述了上面判断 2 注意 因m为机M的磁带符号数为常数 故Bit与n无关 因而B的长是0 P2 n 99 61 2020 3 25 3 令 因S为机M的状态数是常数 故C的长为O P n 其中式子 C C H的意思是 在瞬时t 磁头正扫描着第i个磁带方格 即H 或者在瞬时t 1 第i个方格中的符号仍是瞬时t时的符号xj 4 下面的D表述了在任一瞬时t 至多可以改变一个磁带方格中的内容 注意 1 i P n 1 j m且1 t P n m为常量 故D的长为0 P2 n 99 62 2020 3 25 5 令 其中 中的l遍及于当机器M扫描着xj且处于状态qk时所有可能的下一动作 即是说 对每一 qk xj 有一l值使xjl x qkl q且il为i 1 i i 1分别以d为L S或R而定 为机M的下一动作函数 注意 因为M是不确定的 故可能有多于一个的 但在任何情况下却只能有至多某一有穷常数C个 故Eijkt的长被一常数囿界而与n无关 这里的Eijkt判断了下面的四个命题中 至少 有一个成立 99 63 2020 3 25 在瞬时t第i号磁带方格中不是符号xj 在瞬时t磁头并不扫描着第i号磁带方格 在瞬时t M没有处于状态k 或M的下一格局是依据M的下一动作函数从上一格局而获得的 置 注意 i j k t的变化区域 可知E的长为O P2 n 则E表述了上述判断 5 99 64 2020 3 25 意思是在开始时其余磁带方格为空符号 这里不妨假定x1是空白符 显然 F的长度为0 P n 6 令 这里 S 1 0 是说在瞬时0 M处于状态q1 而q1是M的开始状态 而H 1 0 说在瞬时0 M扫描着第1号方格 意思是前n个磁带方格中打印着输入的字w 最后 7 取G S s P n 这里qs是M的停机状态 则G说该计算路之最后一个格局是停机格局 99 65 2020 3 25 令w0 ABCDEFG 注意上面的各个叙述 得w0的长为0 P3 n 假若不是把一个命题看作一个单独的符号 而是用2进码来表示命题变元 则w0的长将为0 P3 n logn 可用cnP3 n 来囿界 换言之是多项式囿固界的 显然 当已给定w和多项式P时 可用上述算法在cnP n 步内写出输出w0 同时 下述事实也是完全明白的 给定一个可接受的计算路Q0 Q1 Qg 可在w0中找到命题变元C i j t S k t 与H I t 的指派使w0被满足 反之 若有一个使w0被满足的指派 则可由此找到可接受的计算路 故w0可满足 M接受w L 最后 注意到上述构造中并未对语言L做任何限制 只是假定L NP 这样 便证明了 命题逻辑的可满足问题是NP完全的 99 66 2020 3 25 Cook定理的重要意义 Cook定理是NP完全理论中非常重要得一个定理 这是因为 首先 它以实例说明NP完全问题是存在的 其次 它给出了判断某一其它NP问题 更确切地说是表现为这一类问题的语言 L0是否是NP完全的捷径 即不必按定义7 12证明 即只须证明 这是因为 所有L NP 再由上式和多项式变换的传递性 引理7 2 可得 一旦证明了L0是NP完全的 则它又可发挥SAT同样的作用 99 67 2020 3 25 NP完全性的证明过程 从现在起判定问题 的NP完全性的证明过程将由下述三步组成 证明 属于NP 选择一个已知的NP完全问题 构造从 到 的多项式变换函数f 99 68 2020 3 25 7 6强NP完全问题 在实际中 绝大多数判定问题的描述都或多或少地包含有一些数字型参数和分量 进而 对这类判定问题中的大部分而言 其求解的难易程度 相应求解算法的时间复杂性等 常常都受到判定问题任一具体实例中所含数字参数的值的大小的严重影响 特别是其中出现的最大的整数的具体值 该值的大小往往会使判定问题相应实例求解的难易性 或所用求解算法的时间复杂性函数发生某种质的变化 对于这样的判定问题 仅仅使用表示其某个实例I的输入长度的函数Lengh I 就无法全面客观地衡量实例I的大小己求解的困难程度 为此 人们就引入了另外一个函数Max D Z 并通常Max I 的值为I中所出现的最大整数的具体值 利用函数Length和Max 我们就可以给出另一类比NP完全问题还要难于求解的问题的定义 即所谓的强NP完全问题 99 69 2020 3 25 伪多项式时间算法 定义7 6 1如果解问题 的算法的时间复杂性函数不超过两个变量Length I 和Max I 的多项式函数 则称这个算法是关于 的伪多项式时间算法 根据定义 任何多项式时间算法也是伪多项式时间算法 因为它的运算时间不超过只是Length I 的多项式 但是 实际中的还有许多不是多项式时间算法的伪多项式时间算法 我们用下述解整数背包问题的方法来加以说明 99 70 2020 3 25 整数背包问题 实例 给定整数c1 c2 cn以及整数b 问 是否存在整数x1 x2 xn 0 使得 已经证明该判定问题是NP完全的 参见8 2 1节 令cj aj j 1 2 n 现给出求解它的一个伪多项式时间算法 先构造一个有向图G c1 c2 cn b V E 如下 V 0 1 2 b E 0 m k b 且对某个j n k m cj 于是G有b 1个结点 O nb 条边 显然这一构造过程可在O nb 时间内完成 下面我们证明图G c1 c2 cn b 有一条从0到b的通路当且仅当上述整数背包问题的判定问题的实例 c1 c2 cn b 有一个解 99 71 2020 3 25 设 0 i0 i1 i2 im b 是G中的一条通路 考虑序列 y1 y2 ym i1 i0 i2 i1 im im 1 则由G的定义知y1 y2 ym全在 c1 c2 cm 之中 且 从而有非负整数解 即将xj取成cj在 y1 y2 ym 中出现的次数 反之 如果对于非负整数x1 x2 xn有 那么通过取 我们就会在G c1 c2 cn b 中重新找到一条从0到b的通路 这条通路是 0 i0 i1 i2 im b 其中 99 72 2020 3 25 对于上述构造的图G 利用图论中寻找通路的算法 我们可以在O nb 时间内确定是否存在一条从0到b的通路 综上所述 我们已经证明了整数背包问题的任何实例 c1 c2 cn b 均能用上述的算法在O nb 时间内解决 显然这是一个伪多项式算法 关于强NP完全性与伪多项式算法之间的关系 我们有以下结论 99 73 2020 3 25 定理7 6 1 除非P NP 不然任何强NP完全问题都不会有伪多项式时间算法 证明 设 为强NP完全问题 换言之 对于某个多项式p n p n 是NP完全的 此外设 有一个伪多项式时间算法A 它能在某个双变元多项式q Length I Max I 的时间内求解 的任何实例I 于是 A就在多项式q n p n 时间内求解了NP完全问题 p n 除非N NP 则由NP完全的定义知这是不可能的 因此 证明一个问题是强NP完全的 不仅排除了求解它的多项式时间算法的存在性 而且也排除了其伪多项式时间算法的存在性 基于上述定理 我们也可以将强NP完全问题定义为这样一些NP完全的问题 对于它们 伪多项式时间算法的存在性将意味着P NP 99 74 2020 3 25 基于多项式变换 我们在上节中指出了证明某一问题为NP完全的一种简便而直接的方法 对于强NP完全问题 我们自然希望也能有这样一个好的证明方法 这就要用到下列关于伪多项式变换的概念 令 和 表示任意两个判定问题 实例集合分别为D 和D 是 的集合分别为Y 和Y 并且分别规定函数Max Length和Max Length 从 到 的伪多项式交换是一个满足下述条件的函数f D D a 对于所有的I D I Y 当且仅当f I Y b 能够在两个变量Max I 和Length I 的多项式时间内计算f c 存在多项式q1使得对所有的I D q1 Length f I Length I d 存在两个变量的多项式q2使得对所有的I D Max f I q2 Max I Length I 99 75 2020 3 25 定理7 6 2 如果 是强NP完全的 NP 并且存在一个从 到 的伪多项式变换 那么 是强NP完全的 证明 设f是这样一个伪多项式变换 q1和q2是定义中所规定的两个函数 不失一般性 我们可以假定q1和q2只有正整数系数 因为可以修改这些多项式 只要不减少它们的值 因为 是强NP完全的 所以有一个多项式P使得 p是NP完全的 而且 我们可以选取P使得它只含有正整数系数 因为如果p0是任意一个整系数多项式 对所有x都有p0 x p x 那末 p0将包含 p的所有实例 从而只要 p是NP完全的 p0也一定是NP完全的 设p1是如下定义的多项式p1 x q2 p q1 x q1 x 99 76 2020 3 25 我们断言 当限制在 p的实例上时 函数f变成从 p到 p1的多项式变换 于是证明了 p1是NP完全的 首先让我们来看f把 p的每一个实例I映射到 p1的一个实例 根据 p的定义和q1 q2所满足的不等式 对 p的每一个实例I Max f I q2 Max I Length I q2 p Length I Length I q2 p q1 Length f I q1 Length f I p1 Length f I 于是f I 是 p1的一个实例 其次 根据伪多项式变换的定义中的条件 a 和 b 以及 p的每一个实例I都满足Max I p Length I 可立即推出f符合多项式变换的其余要求 因此 p1是NP完全的 从而得证 是强Np完全的 99 77 2020 3 25 结论 这个定理不仅告诉我们在证明某一新问题 的强NP完全性时 并非一定要处理另一已知为强NP完全的问题 的具体例子问题 p 而且 象定理7 6 2的结论一样 它给我们提供了一个利用伪多项式变换来证明强NP完全性的直接而简便的 类似于NP完全情形的方法 99 78 2020 3 25 7 7Co NP类问题 在前面讨论的问题类 特别是P和NP的定义中 我们只考虑求解或检验判定问题回答为 是 的实例所需的时间 而对于那些答案为 否 的实例 情况如何呢 能否用同样的方法 在相同的时间界内求解回答为 否 的实例呢 回答这些问题可从更一般的角度进行分析 我们有如下定义 定义7 7 1对任一判定问题 D Y 都有一个相对应的称为该问题的补或余的另一个判定问题 其中 99 79 2020 3 25 哈密顿回路问题 HC 的补 实例 图G V E 问 G是否不存在哈密顿回路 为了证明G不存在哈密顿回路 需要给出G中结点所有可能的排列 并且验证这些排列都不是回路 这和验证G存在哈密而顿回路不同 前者必须检查所有的排列 而后者只需检查一个排列 当G存在哈密而顿回路时 总可以假设猜对了 检查所有排列不可能在多项式时间内完成 事实上 至今不知道是否在NP中 为了区分 说明这一现象 我们引入如下的问题类 99 80 2020 3 25 Co NP与Co P 定义7 7 2Co NP NP Co P P 人们猜想 NP Co NP 但对于Co P 下面定理保证了P Co P 99 81 2020 3 25 定理7 7 1 如果 是P类问题 那么 的补也是P类问题 证明 因为 是P类问题 因此存在解 的多项式时间算法 解的多项式时间算法恰好是求解 的同一算法 只是每当先前回答 是 的时候 现在就回答 否 反之亦然 因此 若判定问题 P 则有 NP Co NP 即PNP Co NP 但对于NP完全问题则不同 具体有如下定理 99 82 2020 3 25 定理7 7 2 如果一个NP完全问题的补是NP的 那么NP Co NP 证明 假设有一个NP完全问题 0 它的补0是NP的 我们将证明 任何NP问题 的补也是NP的 因为 0是NP完全问题 故 可多项式变换到 0 而这个变换也构成从到0的多项式变换 于是能给出的任意回答为 是 的实例的简短检验 即可在多项式时间内完成论证 它由生成0的回答为是的实例的多项式变换的运算过程和的0该实例的证明过程组成 因为0是NP的 这样的多项式时间内可检验的论证存在 且因变换是多项式时间的 故整个证明就是多项式时间的 所以是NP的 因 是任意的NP问题 故推出NP Co NP 类似地可以证明 若NP Co NP 则亦有NP Co NP 99 83 2020 3 25 各类问题间的关系 于是 NP完全问题是那样一些问题 它们的补很可能不是NP的 反之 如果一个NP问题的补也是NP的 就表明该问题不是NP完全的 综合以上各节讨论有关猜想 我们可以用下图来表示各类问题之间的关系 99 84 2020 3 25 三个未解决的问题 需要指出 到目前为止 对下面三个问题 P NP Co NP吗 Co NP NP吗 P NP吗 其答案仍然是未知的 故上述关系及一切有关结论均是在假设对这三个问题的回答都是 否 的前提下建立的 显然 对 3 的肯定意味着对 1 和 2 的肯定回答 同时 对 1 和 2 的回答 是 则意味着对 3 的答案也是 是 99 85 2020 3 25 7 8NP困难问题 为了给出这类问题的定义 我们需要一个比多项式变换更一般的称为多项式时间图灵归约的概念 这一概念的严格定义需要对确定型图灵机做另一修改 增加一个用于预测 咨询功能的外部信息输入带 而有限状态控制器同时作用于这两个带上 这里略去这一过程 直接在判定问题层次上给出其定义 定义7 8 1设 1和 2都是判定问题 如果存在 1的一个算法A1 它多次调用求解 2的算法A2作为其子程序 而且若假设每次调用该子