作者moonshade (To code or not to code?)
看板ask
标题Re: [问题] NP-complete 和 NP-hard 有何不同?
时间Wed May 26 03:32:49 2004
※ 引述《lufool (愚者)》之铭言:
: NP 基本的定义 我在网路上找得到
: 可是没有上述两者差别的比较....
: 我还是不懂....希望有那位好人能告诉我啊~~~
NP-complete是一个 class
所有的NP problem 都可以reduce 到任一个NP complete problem
就是说你有任何一个可以解NP-complete problem的algorithm
都可以经由log space transform 把一个NP 问题转换成NP-complete 问题
的格式,由这个NP-complete algorithm 来解这个格式的问题
hardness 是说 有一个class 叫做C
另外有一个问题,在这个class 中的所有问题都可以reduce 到这个问题
称这个问题为C hard
这个问题不见得要在C class里
所以NP-complete 的问题一定是NP-hard
不过NP-complete 是一个close under reducetion 的class
NP-complete问题可以reduce 过去的问题一定是NP-complete
--
不知道你有懂吗???
以前上compleity 也是搞很久..
--
有人常问我为什麽喜欢念数学,我总是说:「兴趣啊!」
其实我心里是这麽想的。如果我年老的时候如果我跟孙子说:「爷爷
当年的电子学、积体电路设计学的很棒。」
到时候他们头上大概会升起一堆问号,因为到那个时候这些东西早就不知道去哪里了。
可是如果我说:「爷爷当年学了高微、机率论、实变数论、拓朴...」
他们一定会跟我现在的同学一样,眼睛瞪的大大地说:「干!你是疯子吗?」
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 203.203.32.249
※ 编辑: moonshade 来自: 203.203.32.249 (05/26 03:33)
1F:推 lufool:谢谢你了...我回去好好思考思考...呜.. 140.125.44.121 05/26