不好意思 我又來問問題了 請版大能否幫我解除心中的疑慮
問題是這樣子的，就我所知要證明某問題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
1.1 因為小弟目前現階段要證明出自己的問題是跟2DBP問題是一樣困難的，所以現在卡
在證明NP-hard的部份，因為要找出一個已知NPC問題的Q'，這個問題Q'我不知道能
不能夠用2DBP的問題來做已知的NPC問題<因為不確定>，所以想問個清楚一下。
2 這幾天在google上面找了許久，想找出有人是否證明出2DBP問題是很難的問題，但
得到的結果都是在求解出Approximation的答案<這部份小弟我真的完全不懂>，所以
想請問版大是否能有那種應用簡單的證明<ex:我前面所講的證明NP-complete的過程>
來證明出2DBP是種很難的問題呢??
說了很多，不知道版大是否清楚，因為本身是無線領域的，所以可能提出的問題
不是很專業，請版大多多見諒:D
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 120.107.164.245