第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 是一样的