作者mistel (Mistel)
看板Grad-ProbAsk
标题[理工] 演算法 NP COMPLETE
时间Tue Oct 1 00:33:42 2019
第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差异点是什麽呢？
怀疑人生....
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.137.50.75 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1569861224.A.F24.html
1F：→ DLHZ: 没特别指名应该就是全部 10/01 08:09
2F：→ DLHZ: 如果这样说的话2c看起来无误？ 10/01 08:15
3F：→ DLHZ: sat是指某个公式是不是satisfiability 应该没特别要求几个 10/01 08:16
4F：→ DLHZ: 14我想看一下完整的题目 10/01 08:50
5F：→ DLHZ: 16.2他有提到 正权重longest path等价於负权重shortest path 10/01 09:19
6F：→ DLHZ: interval graph就是用一些实数长度的线组成的graph 10/01 09:21
7F：推 FRAXIS: 14 因为是 undirected graph 所以每条边 weight 都是 1 10/01 11:04
8F：→ FRAXIS: 16 (2) 题目已经说了 是 shortest simple path 10/01 11:05
9F：→ FRAXIS: 所以有解 无解的是找 shortest path 因为你可以在 10/01 11:06
10F：→ FRAXIS: negative cycle 上一直绕圈 10/01 11:06
11F：→ FRAXIS: 25 题目写的是 instance, SAT 问题很难 因为现在找不到 10/01 11:08
12F：→ FRAXIS: 一般性的方法可以有效率的解所有 instance 10/01 11:08
13F：→ FRAXIS: 但是不代表所有 instances 都很难解 像是 SAT 的特殊形式 10/01 11:09
14F：→ FRAXIS: 2-SAT 就很容易解 10/01 11:09
15F：→ FRAXIS: 3-SAT 是 SAT 的特例 但是难度跟 SAT 是一样的 10/01 11:10