World's most popular travel blog for travel bloggers.

Is the MinMax/optimization/search variant of a decision problem always easier/equal?

, , No Comments
Problem Detail: 

Is the MinMax/optimization/search variant of a decision problem always easier/equal in complexity because we can always reduce them to their decision variant?

From Wikipedia:

If the longest path problem could be solved in polynomial time, it could be used to solve this decision problem, by finding a longest path and then comparing its length to the number k. Therefore, the longest path problem is NP-hard. It is not NP-complete, because it is not a decision problem.

Is the max-variant of this problem only NP-hard because the decision-variant is also NP-hard (and NP-complete)? (and not because it is harder)

What about polynomial time problems? If the decision variant of a problem is in P, I would assume that the optimization variant is not NP-hard, because that would imply P = NP. Do we say that it is in P then, or is it in another class/no class?

Asked By : user1377493

Answered By : D.W.

No. A reduction only proves that it is "at least as hard", not that it is easier. Normally, the optimization problem is approximately as hard as the corresponding decision version (to within a polynomial factor).

If the decision problem is in P (can be solved in polynomial time), and there's a polynomial time reduction from the optimization problem to the decision problem, then that implies that the optimization problem can be solved in polynomial time. It's not literally in P, because P is a class of decision problems, but you can think of it as being in some class that is analogous/similar to P.

It's not clear to me what you mean by "the MinMax variant" or "the max-variant", so I can't answer that part.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback