作者xcycl (XOO)
看板Math
標題Re: [演算法]關於NP問題
時間Thu Aug 13 02:48:36 2009
※ 引述《NGboy (今天我NG了)》之銘言：
: 想請問一些關於NP問題的一些疑惑
: 比方說最近在看關於Knapsack Problem，這個問題看了一些文獻中有人說他是屬於
: "NP-complete"，也有人說他是屬於"NP-hard"，想請問到底是那個才是對的呢？
NP-complete 跟 NP-hard 有交集，其實都沒錯。
NP-complete 是指若該問題可在 P 求解，則所有在 NP 的問題都可以在 P 求解。
NP-hard 是指對於問題 T ，存在一個 NP-complete 問題 H，可以在多項式時間內
從 H 簡化成 T。
所以可以看到 NP-complete 的問題照定義，本身也是 NP-hard 的問題。
（自己簡化成自己，不用動就是了）
但是說 NP-complete 會比較明確些。
: 還是說這些NP的問題是否都取決於我們解決此問題的演算法而來決定出來他最終是
: 屬於NP-complete or NP-hard
: 相關的疑惑也存在於two-dimensional bin packing problem.....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.226.9
推 NGboy:大大你說的我都懂 但NP跟NP-hard畢竟不同吧，為何說 08/13 02:55
→ NGboy:為何說NP-complete會比較明確些 這又讓我搞混了 08/13 02:55
→ xcycl:因為所有 NP-complete 問題都是 NP-hard 啊。 08/13 02:56
→ xcycl:然而反過來不成立。 08/13 02:57
推 NGboy:喔～有點恍然大悟的感覺 08/13 03:01
※ 編輯: xcycl 來自: 123.193.226.9 (08/14 01:17)
推 Hseuler:推~ 08/14 21:33
※ 編輯: xcycl 來自: 123.193.216.223 (08/17 00:13)