NP problems verification phase

410 Views Asked by At

I know that a NP problem is a problem where i can verify a result in polynomial time.

However , if i take a problem as the "Minimum vertex cover" it's possible to verify that a solution is a vertex cover, but it's impossible to verify that a solution is a minimum vertex cover.

So, why we say that "Minimum vertex cover" is a NP problem even if it's impossibile to completely verify a result ? In fact, we can only verify the result partially, noting that a solution is a vertex cover or not, but without the possibility to say if a solution is a minimum vertex cover or not.

1

There are 1 best solutions below

3
On BEST ANSWER

You are conflating a few ideas. (This is a common conflation, so no judgment here.)

The class NP is decision problems which have deterministic polynomial time "yes" verifications. Note that the result of a decision problem algorithm is either "yes" or "no", which cannot be a vertex cover (except possibly for a graph with only a single vertex). One way to show that a new decision problem is as hard as NP (or harder) is to show that every instance of an NP-complete problem can be embedded isomorphically as a problem instance of the new problem. (That is, for every instance of an NP-complete problem, this new problem contains an instance whose solution can be translated into a solution of that NP-complete problem. ) To show that it is actually in NP (and not harder), one shows that an algorithm for solving the problem produces a certificate -- a short sequence of bits which can be used by a different algorithm to deterministically verify in polynomial time (in the length of the original problem instance) that the result of the deciding algorithm is correct. For example (using a familiar problem), a certificate that a positive integer is composite would be a pair of positive integers bigger than $1$ whose product is the given integer. This list is about as long as the initial integer and takes at most quadratic time in the length of the initial integer to multiply out and compare with the initial integer.

So the vertex cover decision problem takes a graph and a non-negative integer, $k$, and answers the question "Does this graph have a vertex cover of size $k$?" The algorithm responds "yes" or "no". For "yes" instances, a list of vertices in the cover would be a sufficient certificate. Note that the decision algorithm does not provide an explicit certificate -- the proof merely shows that it could have done so.

The minimal vertex cover problem asks "What is the minimal $k$ such that the vertex cover decision algorithm returns 'yes' for this graph?". We can find this $k$ using a polynomial number of instantiations of the vertex cover problem. Produce a sequence of test $k$s that double in size as long as we get "no" answers, stopping the doubling when we get the first "yes" answer, then continue the sequence of $k$s by binary subdivision of the interval bounded on the left by a "no" instance and on the right by a "yes" instance until we find the least $k$ producing a "yes" instance. This cannot require more calls to the vertex cover algorithm than there are vertices in the graph, so has time complexity some polynomial times the time complexity of your vertex cover algorithm.

Since the output of that "minimal vertex cover" algorithm is a number and not a "yes" or "no", it is not a decision problem, so cannot be an NP problem. However, we can convert it to a decision problem: "Is this $k$ the result of the minimal vertex cover algorithm applied to this graph?" So we may ask if this problem is in NP. This problem is at least as hard as the vertex cover problem, so is at least hard enough to be in NP. For it to be in NP, we need a (short) certificate that allows verification of "yes" instances in polynomial time.

I claim that a sufficient certificate is a list of $k$ vertices which form a vertex cover. This claim rests on one theorem: Every vertex cover of a graph contains a minimal vertex cover. So we can verify that this list is minimal by testing if each subcover made by deleting only one vertex from the list is not also a vertex cover. This takes $k$ calls to your cover verifier, which can be polynomial time in the length of the specification of the graph. Therefore, the decision version of minimal vertex cover is in NP.