※ 引述《xcycl (XOO)》之銘言：
: ※ 引述《NGboy (今天我NG了)》之銘言：
: : 想請問一些關於NP問題的一些疑惑
: : 比方說最近在看關於Knapsack Problem，這個問題看了一些文獻中有人說他是屬於
: : "NP-complete"，也有人說他是屬於"NP-hard"，想請問到底是那個才是對的呢？
: NP-complete 跟 NP-hard 有交集，其實都沒錯。
: NP-complete 是指若該問題可在 N 求解，則所有在 NP 的問題都可以在 N 求解。
^^^ ^^^
P P
: NP-hard 是指對於問題 T ，存在一個 NP-complete 問題 H，可以在多項式時間內
: 從 T 簡化成 H。
: 所以可以看到 NP-complete 的問題照定義，本身也是 NP-hard 的問題。
: （自己簡化成自己，不用動就是了）
: 但是說 NP-complete 會比較明確些。
: : 還是說這些NP的問題是否都取決於我們解決此問題的演算法而來決定出來他最終是
: : 屬於NP-complete or NP-hard
: : 相關的疑惑也存在於two-dimensional bin packing problem.....
重貼定義(wiki)
A decision problem C is NP-complete if:
(i) C is in NP, and
(ii) Every problem in NP is reducible to C in polynomial time.
Problems中只要滿足條件(ii)就稱是NP-hard了
而你的背包問題滿足兩個條件 所以既是NP-C 也會是NP-hard
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.4.16