[理工] 106清大計科 7 8

[bochengchen (LFII)]

請問各位大大

1.
第七題的第四小題
https://imgur.com/u9KXQTy.jpg
這個敘述應該是false，想請問各位大大該如何解釋？


2.
第八題
https://imgur.com/BVt9zsS.jpg
不知道這兩個小題該怎麼做比較好呢？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 124.199.106.66 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578467036.A.556.html
推 zuchang: 這是106的題目 我是抄立宇姐姐的
→ zuchang: https://i.imgur.com/iV0GmpM.jpg
年份已改！ 感謝Ｚ大提供第八題！
※ 編輯: bochengchen (124.199.106.66 臺灣), 01/08/2020 15:28:42
→ zuchang: 7 立宇姐姐也沒給證明 就背下來QQ
→ zuchang: if P !=np 則>=1的approximation algo 都不存在
推 NCTUcs: 第7題是CLRS Theorem 35.3
→ NCTUcs: https://i.imgur.com/T2ZM1OE.jpg
→ NCTUcs: 證明在習題35.2-2
→ NCTUcs: https://i.imgur.com/CdIxjwV.jpg
→ NCTUcs: https://i.imgur.com/RzOKeuR.jpg
→ bochengchen: 感謝交大資工大大