chapter-9np完全问题

《chapter-9np完全问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、9NP完全问题NPCompleteProblem南京理工大学本章内容提要易解问题与难解问题P类问题和NP类问题NP完全问题co-NP类问题NPI类问题P、NP、co-NP、NPI类之间的区别与联系NP完全问题的计算机处理技术简介南京理工大学9.1引言9.1.1易解问题与难解问题如果对一个问题∏存在一个算法，时间复杂性为O(nk)，其中n是问题规模，k是一个非负整数，则称问题∏存在多项式时间算法。这类算法在可以接受的时间内实现问题求解，e.g.,排序、串匹配、矩阵相乘。现实世界里还存在很多问题至今没有找

2、到多项式时间算法，计算时间是指数和超指数函数（如2n和n!），随着问题规模的增长而快速增长。通常将前者看作是易解问题，后者看作难解问题。南京理工大学9.1.2易解问题与难解问题的主要区别在学术界已达成这样的共识：把多项式时间复杂性作为易解问题与难解问题的分界线，主要原因有：1)多项式函数与指数函数的增长率有本质差别问题规模n多项式函数指数函数lognnnlognn2n32nn!1010.01121103.31033.2100100010243628800204.32086.44008000104837

3、62.4E18505.650282.225001250001.0E153.0E641006.6100664.41000010000001.3E309.3E157南京理工大学2)计算机性能的提高对易解问题与难解问题算法的影响假设求解同一个问题有5个算法A1~A5，时间复杂度T(n)如下表，假定计算机C2的速度是计算机C1的10倍。下表给出了在相同时间内不同算法能处理的问题规模情况：T(n)nn′变化n′/n10n100010000n′=10n1020n5005000n′=10n105nlogn25018

4、42n

5、于指数函数值，但n充分大时，指数函数仍然超过多项式函数。南京理工大学9.2P类问题和NP类问题这个划分标准是基于对所谓判定问题的求解方式。先看看什么是判定问题。事实上，实际应用中的大部分问题问题可以很容易转化为相应的判定问题，如：排序问题给定一个实数数组，是否可以按非降序排列?图着色问题：给定无向连通图G=(V,E)，求最小色数k，使得任意相邻顶点具有不同的着色给定无向连通图G=(V,E)和正整数k，是否可以用k种颜色.....?南京理工大学确定性算法与P类问题对判定问题求解，可以采用确定性算法定

6、义9.1(确定性算法):设A是求解问题∏的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法A是确定性算法。特点：对同一输入实例，运行算法A，所得结果是一样的。定义9.2(P类问题):如果对于某个判定问题∏，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个确定性算法，得到yes或no的答案，则称该判定问题∏是一个P(Polynomial)类问题。事实上，所有易解问题都是P类问题。南京理工大学定义9.3(非确定性算法):设A是求解问题∏的一个算法，如果算法

7、A以如下猜测+验证的方式工作，称算法A为非确定性(nondeterminism)算法：猜测阶段：对问题的输入实例产生一个任意字串y，在算法的每次运行，y可能不同，因此猜测是以非确定的形式工作。这个工作一般可以在线性时间内完成。验证阶段：在这个阶段，用一个确定性算法验证两件事：首先验证猜测的y是否是合适的形式，若不是，则算法停下并回答no；若是合适形式，则继续检查它是否是问题x的解，如果确实是x的解，则停下并回答yes，否则停下并回答no。要求验证阶段在多项式时间内完成。非确定性算法与NP类问题南京理工

8、大学注意对非确定性算法输出yes/no的理解：若输出no，并不意味着不存在一个满足要求的解，因为猜测可能不正确；若输出yes，则意味着对于该判定问题的某一输入实例，至少存在一个满足要求的解。南京理工大学NP类问题定义9.4(NP类问题):如果对于判定问题∏，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个非确定性算法，得到yes/no的答案，则该判断问题∏是一个NP(nondeterministicpolynomial)类问题。