想请问以下几题，顺便对下答案
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)