# Which of these problems is not in NP? [closed]

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?

• Why do you think so? Check the definition of NP! Some of our reference questions may shed some light on this, too. – 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.