第25題
請問SAT到底是特別指3-SAT還是所有的satisfiability problem ？
如圖
https://i.imgur.com/7rf0leg.jpg
https://i.imgur.com/Ulb09MI.jpg
圖一詳解範例舉2-SAT不是NP-COMPLETE
但圖2(c)選項說3-SAT problem as difficult as SAT
看過維基，SAT應該是3-SAT？
第14題
https://i.imgur.com/FJaOnAV.jpg
請問problem 2為什麼是shortest path problem？ 即使使用folyd warshall也不會保證拜
訪所有邊恰一次吧？
第16題
https://i.imgur.com/VkAnOZn.jpg
https://i.imgur.com/jeJCd6c.jpg
請問選項（2），有負cycle不是無解嗎？為什麼是NP-COMPLETE？
再請問選項（9）的interval graph是什麼？
另外，選項（5）跟前面第14題的問題2差異點是什麼呢？
懷疑人生....

沒特別指名應該就是全部如果這樣說的話2c看起來無誤？sat是指某個公式是不是satisfiability 應該沒特別要求幾個14我想看一下完整的題目16.2他有提到 正權重longest path等價於負權重shortest pathinterval graph就是用一些實數長度的線組成的graph

14 因為是 undirected graph 所以每條邊 weight 都是 116 (2) 題目已經說了 是 shortest simple path所以有解 無解的是找 shortest path 因為你可以在negative cycle 上一直繞圈25 題目寫的是 instance, SAT 問題很難 因為現在找不到一般性的方法可以有效率的解所有 instance但是不代表所有 instances 都很難解 像是 SAT 的特殊形式2-SAT 就很容易解3-SAT 是 SAT 的特例 但是難度跟 SAT 是一樣的