推 Hseuler:都算數學吧XD 08/13 19:46
推 evilpigcow:B比較難 08/14 12:55
難得看到演算法的問題，也許試著說明看看！
※ 引述《weeeeeeeeell ( ")》之銘言：
: ※ 引述《xcycl (XOO)》之銘言：
: : 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 會比較明確些。
: 重貼定義(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
目前一般課本的定義是跟 wiki 一樣的，
也就是說，當我們說一個問題 C 是 NP-hard 時，
是說任何在 NP 裡的問題，都能在多項式時間內 reduce 到 C。
換句話說，只要 C 這個問題能在多項式時間內可解，
所以 NP 中的問題也都能在多項式時間內可解！
這其實也是這個觀念很重要的原因：
「只要對任何一個 NP-hard 的問題有多項式時間的演算法，
則任何 NP 裡的問題，都擁有多項式時間的演算法！」
而 NP-complete，是指當一個問題 C 是 NP-hard，
且同時 C 自己又是在 NP 裡。
換句話說，我們可以把 NP-complete 的問題想成是 NP 當中「最難的問題」，
因為按照 NP-hard 的定義，只要能很快的解掉它，
就能很快的解決所有 NP 中的問題！
NP-complete 問題一大堆，有興趣可以看 wiki 上 NP-complete 頁面，
底下有個 List of NP-complete problems :]
另外一個有趣的問題就是，當我們說 Problem A reduces to Problem B，
到底是 Problem A 難？還是 Problem B 難？
也許留給大家想想，之後再說:]
--
computational complexity 還有 algorithms 算不算這個版的討論範圍呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.50.43.141