I see one solved ex on Algorithms.

Which of the following is in NP?

  1. Decision Version of TSP

  2. Array is Sorted?

  3. Finding the maximum flow network

  4. Decision version of 0/1 knapsack?

This Ex Says Three of these problem is in NP. I Think all of them is in NP. Any expert could verify?

  • $\begingroup$ Why do you think so? Check the definition of NP! Some of our reference questions may shed some light on this, too. $\endgroup$ – Raphael Apr 19 '15 at 20:17

In fact, checking whether an array is sorted can be done in time $O(n)$, and there are efficient (polynomial time) algorithms for computing the maximum flow as well. On the other hand, the traveling salesperson problem is known to be NP-hard, as is the knapsack problem.

However, that is not what your question is about. Finding the maximum flow is not a decision problem, and so it is not eligible for being in NP. All other problems are decision problems, and as the preceding paragraph demonstrated, they are all in NP (one in them is even in P, and the other are NP-complete).

| cite | improve this answer | |
  • $\begingroup$ for (3) there is polynomial time solution, which means that it is in P. Thus, it is in NP. $\endgroup$ – M. holi Apr 18 '15 at 19:11
  • $\begingroup$ No. Only a decision problem can be in P or in NP. Maximum flow is in FP, the class of functions computable in polynomial time. It is a type mismatch to ask whether Maximum flow is in P. $\endgroup$ – Yuval Filmus Apr 18 '15 at 19:14
  • $\begingroup$ can we say there is Max -Flow is (decision verison) in NP, and Np-Hard or Np-Complete of it, depends on NP=P or p!=NP? $\endgroup$ – M. holi Apr 18 '15 at 19:21
  • 2
    $\begingroup$ Since Maximum flow is in FP, any reasonable decision version of Maximum flow is in P. $\endgroup$ – Yuval Filmus Apr 18 '15 at 19:38
  • 3
    $\begingroup$ @M.holi No, the answers at that question that claim that non-decision problems are in NP are wrong. $\endgroup$ – David Richerby Apr 19 '15 at 15:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.