NP完全问题

2.2 NP类问题
2.2.1 非确定算法举例 2.2.2 NP类问题算法的阶段 2.2.3 NP类判定问题的定义 2.2.4 NP类问题举例 2.2.5 NP类问题的特征 2.2.6 P类问题和NP类问题的关系
2.2.1 非确定算法举例
给定n个城市及其邻接费用矩阵，找出一个长度为n的序列， 每个元素代表一个城市： int[] getSequence(int n, int[] cities){ int[] result = new int[n]; for (int i=0; i<n; i++){ result[i] = (int)(Math.random()*n); } return result; } 这是一个多项式级别的算法，返回的序列长度为n，但不能 保证相邻两个城市之间有通路，也不能保证各个城市只经过 一次 也可以用城市之间有通路作为条件生成一个长度是n的序列， 这能保证两个相邻城市之间有通路，但不能保证经过且只经 过每个城市一次。这也可以在多项式级别的时间内完成
2.1.5 判定问题规约的定义
定义：令Π和Π′是两个判定问题，如果存在一个 具有如下性能的算法A，可以用多项式的时间，把 问题Π′的实例I′转换为问题Π的实例I，使得I与I′的 Π′ Π 答案一致，就称Π′以多项式时间规约于Π，记为 Π′ ∝p Π 举例：Π问题是：给定一个长度为n整数数组D 和一个整数k判断是否存在D中的一个元素和k相等。 Π′问题是：给定一个长度为m整数数组E和一个整 数k判断是否存在E中的两个元素，其和与k相等。 用于Π′的实例I′向Π的实例I转换的多项式算法A
1.2 问题分类
有两类问题，一类是判定问题，另一类是优化问题 判定问题的解只涉及两种情况：yes或no；优化问题 则涉及极值问题 判定问题举例：给定一个带整数权的有向图G和一 个正整数k，是否存在着一条长度小于k的哈密尔顿回 路？ 优化问题举例：给定一个带整数权的有向图G，其 最短路径长度的哈密尔顿长度是多少？
对于哈密尔顿回路问题Π′ 中的无向图G=(V,E) ，可以 用多项式时间构造新的无向图G′=(V′,E′) ，使得V′=V， E′=E 。对于E′中的每条边(u, v)赋予如下权值：
2.1.3 在补集下封闭的定义
可以把前述判定问题的提法改变：给定两个大 小均为n的集合A和B，判断这两个集合中是否不 存在着相同的元素？ 这个问题是前述问题的补 定义：令C是一类问题，如果对C中的任何问 题Π∈C，如果Π的补也在C中，则称C类问题在 补集下封闭
2.1.4 P类问题在不集下封闭定 理
例二：m团问题CLIQUE：给定无向图G = (V, E)、 正整数m，判定V中是否存在m个顶点，使得它们导 出的子图构成一个完全图 推测阶段：可以随机地找出m个顶点（这些顶点 可以重复）；也可以随机地找出m个不重复的顶点。 这项工作的时间复杂度是多项式级别的 验证和判断阶段：验证m个顶点是否不重复（对 第二种推测，可以省略该步），如果不重复，对于 这m个顶点，判断它们在原图中是否两两相邻。如 果是，则回答yes；否则，回答no。这项工作也可以 在多项式级别的时间内完成
2.2.5 NP类问题的特征
NP类问题的本质特征是：对于给定的一个 实例，能够以多项式时间判断它是不是问题 的实例；如果是，能够以多项式时间对它作 出问题中要求的yes或no的结果回答 NP问题的另一个特征是多项式级别的推测： 能够以多项式时间推测问题的实例
2.2.6 P类问题和NP类问题的关 系
计算复杂性理论有两个基本论题：Church-Turing论题和 Cook-Karp论题 Church-Turing论题：一个问题时可计算的当且仅当它在 图灵机上经过有限次计算得到正确的结果。这个论题把人 类所面临的问题分为两类：一类是可计算的，另一类是不 可计算的。但“有限次计算”是一个宽松的条件 Cook-Karp论题：一个问题是实际可计算的当且仅当它 在图灵机上经过多项式时间（步数）计算得到正确的结果。 Cook-Karp论题将可计算问题类进一步划分成两类：一类 是实际可计算的，另一类是实际不可计算的
3.1 NP完全问题的定义 3.2 多项式规约关系的传递性定理 3.3 NP完全性的传递性定理 3.4 NP完全性的传递性举例 3.5 NP完全问题的重要特征 3.6 NP完全问题举例
3.1 NP完全问题的定义
定义：令Π是一个判定问题，如果对NP中每一个 问题Π′∈NP，有Π′ ∝p Π，就称问题Π是一个NP难题 定义：令Π是一个判定问题，如果Π属于NP，并 且对NP中每一个问题Π′∈NP，有Π′ ∝p Π，就称判定 问题Π是NP完全的，记为NPC 性质：NP难题包含NP完全问题。但有些NP难题 不是NP完全问题，因为它可能不在NP问题中
2.2.3 NP类判定问题的定义
定义：如果对某个判定问题Π，存在着一个非负 整数k，对输入规模为n的实例，能够以O(nk)的时 间运行一个非确定的算法，得到yes或no的答案， 则该判定问题Π是一个NP类判定问题 NP类判定问题的推测和验证合成之后是一个非 确定的算法，这个非确定的算法必须在多项式时 间内完成 NP的意义是：Nondeterministic Polynomial
定理：P类问题在补集下是封闭的 证明：对于P类问题中的任意问题Π，只要修 改相应的多项式级别算法A的代码，把返回yes的 A yes 改为返回no，把返回no的改为返回yes即可
boolean judgeEqual(int n, Elem[] a, Elem[] b){ for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (a[i] == a[j]) return yes; //修改为no return no; //修改为yes }
3.4 NP完全性的传递性举例
已知哈密尔顿回路问题是一个NP完全问题， 证明货郎担问题也是一个NP完全问题 哈密尔顿回路问题Π′ ：给定无向图G=(V,E)， 是否存在一条回路，使得图中每个顶点在回路中 出现且只出现一次 货郎担问题Π：给定n个城市和它们的距离矩 阵，以及距离L，是否存在从某个城市出发，经 过每个城市一次且仅一次，最后回到出发城市且 距离小于或等于L的路线 后面是具体说明：
2.1.6 判定问题规约的定理
定理：令Π和Π′是两个判定问题，如果Π∈P，并 且Π′ ∝p Π，那么Π′∈P 证明：根据Π′和 Π的规约特性，存在着多项式 算法A，把Π′的实例I′转换为Π的实例I，并且二者。A的运算结果（就是I）是一个多 项式规模的结果。而Π的实例可以用多项式规模的 时间运算得到结果。处理Π′的实例I′所需时间是： I′向I转换所需时间 + 处理I所需时间，这两个时间 都是多项式级别的，因此处理Π′的实例I′是多项式 级别的
从定义上看：P类问题可以用多项式时间的确定 算法解决（判定或求解）；NP类问题可以用多项 式级别的时间的确定算法进行检查、验证和判定 PNP。这是因为P类问题一定可以用多项式时 间的算法判定 猜测NP≠P，也就是猜测至少存在着一个问题， 它属于NP类，但它不属于P类。但迄今没有给出 证明
3. NP完全问题
3.3 NP完全性的传递性定理
定理：令Π和Π′是NP中的两个问题，使得Π′ ∝p Π。如果Π′是NP完全的，则Π也是NP完全的 证明： 由于Π′是NP完全的，如果令Π′′是NP中 任意一个问题，则有Π′′ ∝p Π′。根据关系∝p的传 递性， Π′′ ∝p Π。并且，Π′′ 在NP中是任意的， 因此，Π是NP完全的
2. P类和NP类问题
2.1 P类问题 2.2 NP类问题
2.1 P类问题
2.1.1 确定性算法 2.1.2 P类判定问题 2.1.3 在补集下封闭的定义 2.1.4 P类问题在不集下封闭定理 2.1.5 判定问题规约的定义 2.1.6 判定问题规约的定理 2.1.7 判定问题规约定理示例
2.1.1 确定性算法
第12章 NP完全问题
1. NP完全问题概述 2. P类和NP类问题 3. NP完全问题 4. co_NP类和NPI类问题
1. NP完全问题概述
1.1 Church-Turing论题和Cook-Karp论题 1.2 问题分类 1.3 优化问题向判定问题的转换
1.1 Church-Turing论题和CookKarp论题
2.1.7 判定问题规约定理示例
Π问题是：给定一个长度为n整数数组D和一个整数k判断是否存 在D中的一个元素和k相等。 Π′问题是：给定一个长度为m整数 数组E和一个整数k判断是否存在E中的两个元素，其和与k相等 假设Π′问题的输入实例I′是一个长度为n=4的数组{2, 4, -1, 8}， 和一个整数3，转换算法A如下： int[] transfer(int n, int[] inst_ba){ int[] inst = new int [n*(n-1)/2]; int count = 0; for (int i=0; i<n; i++) for (int j=0; j<i; j++){ inst[count] = inst_bar[i] + inst_bar[j]; count++; } } 函数transfer输出一个数组{6, 1, 3, 10, 12, 7}，规模是n的多项式 级别。它含有3，因此原问题结果是yes，否则原问题结果为no
2.2.2 NP类问题算法的阶段
一个NP类问题的算法一般分为2个阶段： 第一阶段是推测阶段，第二阶段是验证阶段 在推测阶段，能够以多项式时间得到问题 的一个“推测”实例（不一定是真正实例） 在验证阶段，能够以多项式时间验证推测 阶段所得实例是否是真正的实例。如果不是 实例，则算法结束；如果是实例，则以多项 式时间判定这个实例的结果是yes或no
1.3 优化问题向判定问题的转换
判定问题举例：给定一个带整数权的有向图G和一个正整数k， 是否存在着一条长度小于k的哈密尔顿回路？ 优化问题举例：给定一个带整数权的有向图G，其最短路径 长度的哈密尔顿长度是多少？