→ DLHZ: 沒特別指名應該就是全部 10/01 08:09
→ DLHZ: 如果這樣說的話2c看起來無誤？ 10/01 08:15
→ DLHZ: sat是指某個公式是不是satisfiability 應該沒特別要求幾個 10/01 08:16
→ DLHZ: 14我想看一下完整的題目 10/01 08:50
→ DLHZ: 16.2他有提到 正權重longest path等價於負權重shortest path 10/01 09:19
→ DLHZ: interval graph就是用一些實數長度的線組成的graph 10/01 09:21
推 FRAXIS: 14 因為是 undirected graph 所以每條邊 weight 都是 1 10/01 11:04
→ FRAXIS: 16 (2) 題目已經說了 是 shortest simple path 10/01 11:05
→ FRAXIS: 所以有解 無解的是找 shortest path 因為你可以在 10/01 11:06
→ FRAXIS: negative cycle 上一直繞圈 10/01 11:06
→ FRAXIS: 25 題目寫的是 instance, SAT 問題很難 因為現在找不到 10/01 11:08
→ FRAXIS: 一般性的方法可以有效率的解所有 instance 10/01 11:08
→ FRAXIS: 但是不代表所有 instances 都很難解 像是 SAT 的特殊形式 10/01 11:09
→ FRAXIS: 2-SAT 就很容易解 10/01 11:09
→ FRAXIS: 3-SAT 是 SAT 的特例 但是難度跟 SAT 是一樣的 10/01 11:10