Re: [理工] 106清大計科 7 8
: 這個敘述應該是false，想請問各位大大該如何解釋？
看到原文底下有提到if p!=np, 沒有>=1的approximation algo
但是有點困惑洪捷不是還教2-approximation vertex problem & TSP嗎?
想請問是不是我有搞錯哪裡？
: 2.
: 第八題
: https://imgur.com/BVt9zsS.jpg
: 不知道這兩個小題該怎麼做比較好呢？
這題題目提到given.... 所以我以為是指已知圖G跟k值問是否滿足每點degree >= |S|-k
所以是為一decision problem非求optimal solution
但是爬文看大家的討論都是在證NP-hard
所以想請問是怎麼判斷題目是要求optimal solution呢？
還是說只能以通常這種題目都是要證NP-complete來做判斷？
謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.64.61 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1675135525.A.BD7.html
推
01/31 19:47,
2年前
, 1F
01/31 19:47, 1F
推
02/02 09:58,
2年前
, 2F
02/02 09:58, 2F
→
02/09 19:33,
2年前
, 3F
02/09 19:33, 3F