※ 引述《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)