Explain why the optimization version of vertex cover is not known to be a search problem. Solution. There is no way to verify that a purported solution is the best possible. The decision version is a...

Explain why the optimization version of vertex cover is not known to be a search problem.

Solution. There is no way to verify that a purported solution is the best possible. The decision version is a search problem (when distances are integers) because we could use binary search to find the best solution.