NP problems and need some detail?

I see one solved ex on Algorithms. Which of the following is in NP?

a) Decision Version of TSP 

b) Array is Sorted?

c) Finding the maximum flow network

d) Decision version of 0/1 knapsack?

My Note, says all of these is in NP, anyone could add a bit detail for each one why? and I confusing about 0/1 knapsack, is it NP? NP-HARD? or NP-Complete?

Thanks.

回答1:

They all are in NP, because:

It is verifiable in polynomial time. Given some route, we can easily check whether its length does not exceed the given value.
It is in P class(I think a polynomial time solution is obvious), which automatically means that is in NP.
Again, there is polynomial time solution, which means that it is in P. Thus, it is in NP.
We can verify it in polynomial time, given an appropriate subset. Hence, it is in NP by definition.

About the decision version of the 0/1 knapsack problem: It is in NP. It is also known to be NP-complete(the proof is too long to write here, here is link: proof). It also means that it is NP-hard(any NP-complete problem is NP-hard by definition).

P.S. I assume that "finding maximum flow" means a decision version here.

回答2:

NP means that there is a deterministic algorithm that runs in polynomial time with the size of the problem that can verify a certificate. A certificate can in this context be seen as a possible solution the the problem. The certificate can be generated in non-determinstic polynomial time. For instance for the TSP a certificate can be any path. In that case the verifier needs to verify that the path is Hamiltonian and less than or equal to the given bound.

Something is X-Hard if it is at least as hard as X. For NP-hard, this is formalized by the fact that every problem in NP can be reduced in polynomial time to that problem.

A problem is x-Complete if it is both an element of x and x-Hard. So for NP-complete it means the problem is NP-hard and part of NP as well.

Now the first problem is clearly in NP. One can non-deterministically generate all possible cycles of length n-1 or less and let the verifier check if all cities are visited exactly once and the the total weight is less than or equal to the given length.

The second can even be done without using non-determinism, you simply iterate over the already existing array and check if each element is greater than or equal than the previous one.

The third can be done deterministically as well: there is a Max-Flow algorithm that runs in O(V^2 E).

The last problem is in NP as well: the certificate is here a bitstring per item with 1 meaning the item belongs to the knapsack and 0 if it doesn't. The verifier has to check if the total weight does not exceed the knapsack capacity and whether the total utility value is greater than or equal to the given one.

So all problems are in NP, not all problems are however (necessarily) NP-hard (and thus by extent not NP-complete). In order to prove something is NP-hard it is sufficient to show that there is a reduction from SAT to that problem. Because it is proven all NP problems can be reduced to SAT, if you can reduce SAT in polynomial time to your problem you can transform all problems through SAT. The details can be looked up, but for the following problems, one can construct a reduction from SAT:

Decision problem of the Traveling salesman problem; and
Decision problem of the Knapsack problem

Academically speaking, P and NP only contain decision variants of of the problems. In order to circumvent that problem, they introduced FP and FNP. Here we will assume that FP is "a bit equal to" P (from the context it is clear whether it is a decision variant) and FNP is more or less equivalent but apparently not enough so that people reading the previous comments can understand with equality we mean the "equivalence" to NP. Most algorithm designers (even academic ones) don't make the difference either and say their "algorithm is in P" (whereas they actually mean their algorithm is in FP). You can say this is the "economical view" (in contrast to the "academic view").

So to summarize, the table reads:

Problem                             | P | NP | NP-hard | NP-complete
------------------------------------+---+----+---------+------------
a) Decision Version of TSP          | * | Y  | Y       | Y
b) Array is Sorted?                 | Y | Y  | ?       | ?
c) Finding the maximum flow network | Y | Y  | ?       | ?
d) Decision version of 0/1 knapsack | * | Y  | Y       | Y
------------------------------------+---+----+---------+-------------

In case P != NP (something that is not yet proven, and will probably not been proven in the near future), algorithms for which a deterministic polynomial algorithm exists that solve the problem (not verifying a solution), then determining whether an array is sorted or generating a maximum flow are not NP-hard.

So in case P=NP, the question marks (?) should be Y, otherwise they should be N. The * is the opposite: in case P = NP, then answer is Y, in case P != NP (very likely), * is N.