Decision to Optimization

In the previous examples, we find an optimal answer to solve the decision problem.

How would you use a decision problem to solve the optimization problem?

For example, imagine we have a subroutine for telling us whether there is a spanning tree of a graph that has weight less than w. How can we find the minimum weight efficiently?

Now, how do we find the MST?


next up previous
Next: P Up: NP-COMPLETENESS Previous: Decision Problems