[理工] NP問題

[ssssIssss (O_O)]

想請教三個問題，是P還是NP

1.Find a positive weight directed cycle in a weighted directed graph

2.（修正）Find the smallest cycle in a graph, where the edge-weight is 1 for e
ach edge


3.The 2-CNF-Satisfiability problem

我都認為是NP，不過爬文好像認為是P，想請教一下@@

（出自交大103資演）

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.99
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486442120.A.03C.html
推 histman: 1.weight取負再跑bellman ford可測負cycle 所以是P
所以是只要測出有cycle就好嗎？
→ histman: 2. run Edmond Karp algo可求
二打錯了，我應該是要問
Find the smallest cycle in a graph, where the edge-weight is 1 for each edge
→ histman: 3. 我直接背…
推 HEroKuma: 2cnf是特例 可以用配置圖算出有解無解 一定是P
→ HEroKuma: 3cnf以上都可以reduce成2sat 所以是NPC
原來如此！
推 joeboy: 2cnf可以畫圖解
推 Transfat: 三個都p
→ kyuudonut: 1. 是跑topological吧......
啊，是用DFS然後看back edge？
※ 編輯: ssssIssss (140.112.25.99), 02/07/2017 13:46:02
→ kyuudonut: 都可以找cycle, 至於要正的話可以再額外處理一下
Topological跑完不是是求出先後順序嗎，要如何化為找positive cycle呢？
※ 編輯: ssssIssss (140.112.25.99), 02/07/2017 13:50:44
推 HEroKuma: 2就改良一下floyd shall,看對角線的值就可以知道最小cyc
→ HEroKuma: le大小多少
推 HEroKuma: 1一般應該都是找有無cycle, 找cycle在那這種進階的是屬
→ HEroKuma: 於很難的問題(以前修演算法問助教得到的答案
→ kyuudonut: 抱歉，我要修正一下，topological 可以判斷是否有cycle
→ kyuudonut: 無法找。至於找cycle，例如bellmen-ford，可以從pred
→ kyuudonut: 去尋找，但也僅限於找到"一個"
→ kyuudonut: 也如同你說的，可以用DFS去改良，搭配back edge去找
→ kyuudonut: positive cycle
推 HEroKuma: 正想回這個XD topological無法做代表一定有cycle 故可以
→ HEroKuma: 拿來判斷有無
→ kyuudonut: 但難的是找到全部的 cycle
推 Transfat: 應該是是說，有cycle沒辦法做出topological order吧，說
→ Transfat: 用topological sort判斷有無cycle好像怪怪的
→ Transfat: 對我就是要說HERO大講的XD
→ kyuudonut: 兩個是等價的
→ kyuudonut: 痾,有點會錯意，但其實我就是這個意思...
懂！感謝各位解惑！
※ 編輯: ssssIssss (140.112.25.99), 02/07/2017 14:27:51