Due to the book "Nature of Computation", consider a problem A, if there exists a witness w such that (x, w) is a yes-instance of B, where B is a decision problem in P regarding pairs (x, w), and x is a yes-instance of A, and where |w| = poly(|x|), then this problem A can be classified as a member of the set NP.
So consider the Minimum Spanning Tree (aka. MST) problem, given a spanning tree T, and we are requested to check whether it is the solution for the graph G. Though T can be regarded as the witness w and |w| = poly(|V| + |E|). However, because we don't know the sum of weights of the MST of G in advance, then we have two methods to check this instance.
The first one is to use either Prim's or Kruskal's Algorithm to generate a MST of G and compare its sum of weights with that of T. If they are equal, then this instance is a yes-instance.
The second method may seem a little bit more complicated. We can take advantage of Lemma 3.1. Namely, during each iteration we choose one edge of T and add it in the set T' which is initially empty. Then we check the edges connecting T'.V and (G - T').V. If this edge is the lightest one among those across these two subsets, then we continue this iteration. If not, we just terminate the algorithm and say that T is not a yes-instance. If all the edges in T are checked and there's no termination, we can end the algorithm and say that T is a yes-instance of this problem.
Comparing the above two methods, I'll buy the first one.
No comments:
Post a Comment