Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: NP-hard与NP-complete的区别
发信站: 哈工大紫丁香 (2001年06月03日08:09:55 星期天), 站内信件

我们经常要见到文献中诸如NP-hard或者NP-complete的概念，
那么这两个概念有什么区别呢？
NP-complete问题是NP类中最难的问题，所谓最难，就是指任意
NP问题都可以多项式转化成该问题。因此，如果该问题有多项式
算法，意味着所有NP问题有多项式算法。显然，NP-complete问题必定本身
是一个NP问题。
一个判定问题是Np-hard，当且仅当任意NP问题可以多项式转化为该问题，
但该问题不一定属于NP。(实际上只要选一个NP-complete问题（比如SAT），
证明它可以多项式转化成该问题就足够了。)
因此，一个NP-hard问题如果不是Np-complete问题，那么它比Np-complete
问题更难。

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]