Chapter-9NP完全问题.ppt

9 NP完全问题NP Complete Problem 本章内容提要 易解问题与难解问题 P类问题和NP类问题 NP完全问题 co-NP类问题 NPI类问题 P、NP、co-NP、NPI类之间的区别与联系 NP完全问题的计算机处理技术简介 9.1 引言 9.1.1 易解问题与难解问题 如果对一个问题∏存在一个算法，时间复杂性为O(nk)，其中n是问题规模，k是一个非负整数，则称问题∏存在多项式时间算法。这类算法在可以接受的时间内实现问题求解， e.g., 排序、串匹配、矩阵相乘。 现实世界里还存在很多问题至今没有找到多项式时间算法，计算时间是指数和超指数函数（如2n和n!），随着问题规模的增长而快速增长。 通常将前者看作是易解问题，后者看作难解问题。 9.1.2 易解问题与难解问题的主要区别 在学术界已达成这样的共识：把多项式时间复杂性作为易解问题与难解问题的分界线，主要原因有： 1) 多项式函数与指数函数的增长率有本质差别 2) 计算机性能的提高对易解问题与难解问题算法的影响 假设求解同一个问题有5个算法A1~A5，时间复杂度T(n)如下表，假定计算机C2的速度是计算机C1的10倍。下表给出了在相同时间内不同算法能处理的问题规模情况： 3) 多项式时间复杂性忽略了系数，不影响易解问题与难解问题的划分 9.2 P类问题和NP类问题 这个划分标准是基于对所谓判定问题的求解方式。 先看看什么是判定问题。事实上，实际应用中的大部分问题问题可以很容易转化为相应的判定问题，如： 排序问题 ? 给定一个实数数组，是否可以按非降序排列? 图着色问题：给定无向连通图G=(V,E)，求最小色数k，使得任意相邻顶点具有不同的着色 ? 给定无向连通图G=(V,E)和正整数k，是否可以用k种颜色..... ? 确定性算法与P类问题 对判定问题求解，可以采用确定性算法 定义9.1(确定性算法): 设A是求解问题∏的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法A是确定性算法。 特点：对同一输入实例，运行算法A，所得结果是一样的。 定义9.2(P类问题): 如果对于某个判定问题∏，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个确定性算法，得到yes或no的答案，则称该判定问题∏是一个P(Polynomial)类问题。 事实上，所有易解问题都是P类问题。 非确定性算法与NP类问题 定义9.3(非确定性算法):设A是求解问题∏的一个算法，如果算法A以如下猜测+验证的方式工作，称算法A为非确定性(nondeterminism)算法： 猜测阶段：对问题的输入实例产生一个任意字串y，在算法的每次运行，y可能不同，因此猜测是以非确定的形式工作。这个工作一般可以在线性时间内完成。 验证阶段：在这个阶段，用一个确定性算法验证两件事：首先验证猜测的y是否是合适的形式，若不是，则算法停下并回答no；若是合适形式，则继续检查它是否是问题x的解，如果确实是x的解，则停下并回答yes，否则停下并回答no。要求验证阶段在多项式时间内完成。 注意对非确定性算法输出yes/no的理解： 若输出no，并不意味着不存在一个满足要求的解，因为猜测可能不正确；若输出yes，则意味着对于该判定问题的某一输入实例，至少存在一个满足要求的解。 NP类问题 定义9.4(NP类问题): 如果对于判定问题∏，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个非确定性算法，得到yes/no的答案，则该判断问题∏是一个NP(nondeterministic polynomial)类问题。 ※注意：NP类问题是对于判定问题定义的，事实上，可以在多项式时间内应用非确定性算法解决的所有问题都属于NP类问题。 关于P与NP关系的初步思考 --从字面含义 1) 若问题∏属于P类，则存在一个多项式时间的确定性算法，对它进行判定或求解；显然，也可以构造一个多项式时间的非确定性算法，来验证解的正确性，因此，问题也属NP类。因此，显然有 P?NP 2) 若问题∏属于NP类，则存在一个多项式时间的非确定性算法，来猜测并验证它的解；但不一定能构造一个多项式时间的确定性算法，来对它进行求解或判定。 因此，人们猜测P ≠ NP，但是否成立，至今未得到证明。 9.3 NP完全问题 NP完全问题是NP类问题的子类，一个具有特殊性质与特殊意义的子类。 问题变换 NP类问题在最坏情况下的时间复杂性一般都是快速增长的指数函数。我们希望能够在NP类问题内部找到一种方法，比较两个问题的复杂性。 比较