NP完全问题(纯理论).ppt

第十二章 NP完全问题
什么是好算法?
算法的种类和数量积累到一定程度时,需要对算法进行比较和分类。
什么是好算法?Edmonds,1975年提出了一个被沿用至今的标准。
Edmonds算法标准
Edmonds算法标准指出具有多项式时间的算法为好
算法。
多项式时间算法:如果П是任意一个问题,对П存
在着一个算法,它的时间复杂性为O(nk),其中n为输
入规模,k为非负整数,就认为存在着一个解问题П
的多项式时间算法。
以多项式作为分界函数?
原因有两个:
一、常见算法大致分为两类:
一类是多项式时间内可实现的
另一类需要指数时间())
多项式时间算法的可实现性远大于指数时间算法。
(参见P8,)
以多项式作为分界函数?
二、多项式时间算法与计算模型无关
算法的研究依赖于计算模型。在不同类型计算模型上实现算法,计算时间不同。
广义Church—Turing命题:不同计算模型上的计算时间有多项式关系。
多项式与多项式的复合函数是多项式,因此,多项式时间算法与计算模型无关。
P类问题—易解的问题
是否每个问题都有多项式时间算法?
在考虑问题的计算复杂性时,常把它化为相应的判定
问题考虑。
首先看问题分类及其转换。
问题分类
一类是判定问题
解只有两种,yes或no。
例:给定图G=(V,E), 问该图是否有哈密尔顿圈。
一类是优化问题
例:给定图G=(V,E),假设边的费用为自然数。求该
图的最短哈密尔顿回路。
问题转换
优化问题可转换为相应的判定问题求解。

例:给定图G=(V,E),假设边的费用为自然数。给
定k=1,2,..,问是否有长度不超过k的哈密尔
顿回路。
P类问题
P类:
具有多项式时间算法的判定问题形成一个
计算复杂类,记为P类。

P类—易解的问题
P-Polynomial
思考:已学知识中哪些问题属P类问题?
NP类问题—难解的问题
具有指数时间算法的问题。
例:货郎担问题(TSP问题)。

n!排列方式。
n=6: 6! = 720
n=19: 19! ≈ *1017
每秒排一次,*109年
每秒排百万次,排3000年
有算法但实现性差。