※ 引述《NGboy (今天我NG了)》之銘言：
: 1.我不是很確定二維裝箱問題是NP-hard or NP-complete 本身所看到的文獻這兩個都
: 有人在講，我記得版上有大大跟我說所有的NP-complete問題都是NP-hard問題，
: 只是講說是NP-complete會比較明確一些。但也由於我比較想確切的問個明白，所以
: 在這邊再提出來詢問一次，因為這關係到問題1.1
這裡
http://etdncku.lib.ncku.edu.tw/ETD-db/ETD-search-c/view_etd?URN=etd-0706106-174128
有提到
Bin packing problem is a difficult NP-hard problem even with the
absence of the LIB constraint.
或許將它的全文拿來，可以找到證明的文獻吧！
我想若是論文都找 approximation 答案的話，很可能這是大家已知的 NP-hard 的
問題，若不夠難的話，找 approximation 的解法就沒有道理。
: 1.1 因為小弟目前現階段要證明出自己的問題是跟2DBP問題是一樣困難的，所以現在卡
: 在證明NP-hard的部份，因為要找出一個已知NPC問題的Q'，這個問題Q'我不知道能
: 不能夠用2DBP的問題來做已知的NPC問題<因為不確定>，所以想問個清楚一下。
: 2 這幾天在google上面找了許久，想找出有人是否證明出2DBP問題是很難的問題，但
: 得到的結果都是在求解出Approximation的答案<這部份小弟我真的完全不懂>，所以
: 想請問版大是否能有那種應用簡單的證明<ex:我前面所講的證明NP-complete的過程>
: 來證明出2DBP是種很難的問題呢??
: 說了很多，不知道版大是否清楚，因為本身是無線領域的，所以可能提出的問題
: 不是很專業，請版大多多見諒:D
--
Xuite日誌：http://blog.xuite.net/springman/
網路城邦：http://blog.udn.com/springman
聖經查詢系統：http://springbible.fhl.net/
芳苑教會：http://fychurch.fhl.net/
信望愛bbs：http://wbbs.fhl.net/
自由軟體使用經驗分享 http://springbible.blogspot.com/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.23.24.146