Max Flow and NP, Need some Experts Verify this challenge?
I see this question on NP problems and need some detail?
I studying about NP, P and NP-Complete on Computational Course, and get stuck in one definition:
we have an example to determine following is in NP or not:
Finding the maximum flow network.
someone says " there is polynomial time solution, which means that it is in P. Thus, it is in NP"
someone says "this is not matter that there is no decision problem here. you can find the maximum flow in polynomial time, so in that case, you don't need to generate a certificate first. The problem is clearly in P because of the Ford-Fulkerson algorithm and thus by extend in NP. It's not the decision variant that makes something NP. The point is that you cannot exploit non-determinism to know for sure the certificate is the optimal one"
someone says "Finding the maximum flow is not a decision problem, and so it is not eligible for being in NP"
in this category my main confusing is can we say this problem in in NP or cannot say, because e there is no Decision Problem ? any Idea? or proof ?
链接地址: http://www.djcxy.com/p/40004.html上一篇: P NP和NP完全分类？