※ 引述《bochengchen (LFII)》之銘言：
: 請問各位大大
: 1.
: 第七題的第四小題
:
: 這個敘述應該是false，想請問各位大大該如何解釋？
看到原文底下有提到if p!=np, 沒有>=1的approximation algo
但是有點困惑洪捷不是還教2-approximation vertex problem & TSP嗎?
想請問是不是我有搞錯哪裡？
: 2.
: 第八題
:
: 不知道這兩個小題該怎麼做比較好呢？
這題題目提到given.... 所以我以為是指已知圖G跟k值問是否滿足每點degree >= |S|-k
所以是為一decision problem非求optimal solution
但是爬文看大家的討論都是在證NP-hard
所以想請問是怎麼判斷題目是要求optimal solution呢？
還是說只能以通常這種題目都是要證NP-complete來做判斷？
謝謝！