Re: [問題] NP-complete 和 NP-hard 有何不同？

看板ask (問板)作者moonshade (To code or not to code?)時間21年前 (2004/05/26 11:15)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/1

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