為什麼這篇Np complete鄉民發文收入到精華區：因為在Np complete這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者hcsoso (索索)看板Math標題Re: [演算法] 證明NP-complete時間Fri ...
※ 引述《NGboy (今天我NG了)》之銘言：
: 不好意思 我又來問問題了 請版大能否幫我解除心中的疑慮
: 問題是這樣子的，就我所知要證明某問題Q為NP-Complete 首先要：
: a. prove Q 屬於NP <此步驟是要證明Q是屬於NP>
: b. 找出一個已知的NPC問題Q'，證明出Q'可以reduction成Q <此步驟是要證明Q是屬於
: NP-hard>
: 好了，問題來了，本身小弟我有個問題，這問題短時間解釋不了，只能說這個問題是
: 跟 two-dimensional bin packing problem(二維裝箱問題,2DBP)有相關的
: 我的問題是這樣:
: 1.我不是很確定二維裝箱問題是NP-hard or NP-complete 本身所看到的文獻這兩個都
: 有人在講，我記得版上有大大跟我說所有的NP-complete問題都是NP-hard問題，
: 只是講說是NP-complete會比較明確一些。但也由於我比較想確切的問個明白，所以
: 在這邊再提出來詢問一次，因為這關係到問題1.1
既然 NP-complete 的問題也都是 NP-hard (按照定義)，
所以問題也許出在：我們要怎麼確定一個問題屬於 NP？
所以，首先我們要定義什麼是 NP :]
NP 是一群問題的集合 (嚴謹的定義請見 computational complexity 課本)，
這群問題有一個共同的特性：
「所有在 NP 中的問題，它的證明都可以在多項式時間內驗證。」
很敖口對吧(對不起)
就用你提到的 Bin Packing 舉個例子：
這個問題是給定一堆貨物以及它們的大小 { a_1, ..., a_n }，
假設我們要把這些東西塞進 B 個大小為 V 的大箱子中，
請問有沒有可能？貨物要怎麼安排？
對於這個問題，
我們要想個多項式時間內的演算法是不容易的，
(如果有人想出來了，記得來 PO 板，如果正確的話你可以拿到壹百萬美金)
但是，如果有人已經給你了一個安排的方式，
我們要驗證是很容易的：
只要看他是不是只用到 B 個箱子？
每個箱子是不是只有裝最多為 V 大小的東西？
如果都是的話，他的安排方式就是對的！
這種檢查的方式，是在多項式時間內，
換句話說，我們已經證明了 Bin Packing 這個問題是在 NP 之內了！
至於剛剛先假設的事實 「Bin Packing 是 NP-hard」，
我們就相信他吧(笑)
所以，自此之後，我們就可以說 Bin Packing 是 NP-complete 了:]
2D-Bin Packing 也可以用同樣的方法驗證它在 NP 裡，
所以也是 NP-complete！
: 在證明NP-hard的部份，因為要找出一個已知NPC問題的Q'，這個問題Q'我不知道能
: 不能夠用2DBP的問題來做已知的NPC問題<因為不確定>，所以想問個清楚一下。
有了上面的 Claim，當然 2DBP 就可以拿來當作已知的 NPC 問題囉！
: 2 這幾天在google上面找了許久，想找出有人是否證明出2DBP問題是很難的問題，但
: 得到的結果都是在求解出Approximation的答案<這部份小弟我真的完全不懂>，所以
: 想請問版大是否能有那種應用簡單的證明<ex:我前面所講的證明NP-complete的過程>
: 來證明出2DBP是種很難的問題呢??
有的，其實我們需要的，就是有另一個 NPC 的問題能夠 reduction 到 2DBP，
但因為這是比較早的結果，
也許去翻翻 complexity 的課本，像是
Computers and Intractability: A Guide to the Theory of NP-Completeness
by M. R. Garey, D. S. Johnson
Computational Complexity
by Christos H. Papadimitriou
裡頭也許會有！
(抱歉我也沒有記的很清楚，有更懂這方面的版友知道哪裡會有嗎？)
或是，也許自己造一個 reduction，
當作對證明一個問題是 NPC 的訓練？:]
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.50.43.141
※ 編輯: hcsoso 來自: 123.50.43.141 (08/14 16:55)
推 weeeeeeeeell:補充一下 2DBP有一些不同的版本 舉最初的版本： 08/14 17:01
→ weeeeeeeeell:裡頭的rectangles需平行箱子放 也不能rotate 08/14 17:01
→ weeeeeeeeell:1DBP的確是NP-complete 因為把每箱size就驗證對不對 08/14 17:02
→ weeeeeeeeell:但是2維時 就必需給出一個放法 這個放法在2DBP中是 08/14 17:03
→ weeeeeeeeell:花polynomial time了 08/14 17:04
推 weeeeeeeeell:^^^^^^^^^^^^^^^^^^更正上面這句話如下 08/14 17:07
→ weeeeeeeeell:要花超過polynomial time才能驗證的 08/14 17:07
→ hcsoso:你是對的，如果要給出放法2DBP應該是not known to be in NP 08/14 17:26
→ hcsoso:不過，我們要證明一個問題是 NP-hard，只需要從另一個 08/14 17:35
→ hcsoso:NP-hard 的問題 reduce 過來就行了... 08/14 17:35
推 moon0419:之前修課的時候..我們老師有說過有個網站之類的... 08/14 22:29
→ moon0419:把現今的問題分類的差不多...如果有新的..就照上面說的做 08/14 22:30