想請問以下幾題，順便對下答案
9.假設P不等於NP 當以下問題為P則選1 NP-hard or NP-complete選2 其他選3
(1)Find a longest simple path between two nodes,where the given graph has
positive edge weights.
(2)Find a shortest simple path between two nodes in a directed graph with
negative and/or positive edge weights ,and containing negative weight
cycles.
(3)Find a negative weight directed cycle in a weight directed graph.
(4) "" positive ""
(5)Find a largest cycle in a graph,where the edge-weight is 1 for each edge.
(6) smallest
(7)Find a max-cut in a flow network
(8) min-cut
(9)Find a max independent set in an interval graph
(10)2-CNF SAT problem
想問問大家的答案，目前我寫的是2、7、8、9、10都是NPC，剩下的都不清楚
我很好奇他假設P不等於NP是不是有甚麼陷阱?
還有3既不屬於P又不屬於NPC那是又甚麼??
10.這題有圖片希望大大能自行翻一下
(1)n=8，所以output = 8! ??? (2) ???
↑這題我不曉得要寫甚麼，希望能解釋一下
11.我寫的是F T F F T
12.MAX flow 2+3 = 5，切邊(S,A)(A,C)(C,D)
有些邊流量並沒有滿(如A,C還有1的流量)，就直接切了，可以嗎？
求解，感恩

1, 5, 7是NPC, 如果 P = NP, 那NPC = P 這題就變成多選題不屬於P 又不屬於 NPC 是有可能的 像是co-NP-Hard..

12.不行哦，要算到滿才會是正確解

11.a 若E小比Floyd快,我寫True...

那請問第9題的所有答案是甚麼呢？想確認一下11題的話我是用DS的角度去看得Bellman's跟Floyd均為O(N^2)Dijkstra's為O(n^2)但不可以有負邊12題用BFS來跑流量就找不到切邊的樣子

12.resudual net.cut為c(S,A)+c(C,D)=511.依照cormen bellman+Dijk.:O(VE+VlgE), Floyd O(V^3)11.提及Bell. technique=>使人聯想John.說太細易有bug9.NPC:1,2,4,5,6,7,8,9,10 P:3 (是這樣?3.我想到bellman...O(VE)6.即使weight=1, nC3+nC4+...+nCn=2^n仍屬NP6.cycle至少由3邊構成...至多n6.大碩筆記大部分有整理分類,要感謝之前大大...偉X 爛bellman可得最大負循環?最小負循環稍加修改應該也可以P?或者bellman 只能判斷(找)負循環 最大(小)無法判定(問!

11題因為DS上寫都為O(n^3)所以我才認為是一樣快，寫F但用ALGO來看，邊小的確是Bellman比較快 了解O碩近幾年都沒有DS考古題的詳解，還挺困擾的12題的(a)用Edmonds-Karp求出MAX flow=5但找不出切邊(b)用Ford-Fulkerson求出MAX Flow=4切邊(S,A)(A,C)(C,D)