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

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?

• Always easier/equal in complexity to what? – David Richerby Nov 8 '16 at 20:23
• To their decision variant. – user1377493 Nov 8 '16 at 20:56
• You may be confused by the statement "not NP-complete" - only decision problems are ever called NP-complete. – gnasher729 Nov 8 '16 at 23:49

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.

• I mean, Get the length of the longest path or Get the longest path, instead of the decision variant Is there a path longer or equal to K? – user1377493 Nov 9 '16 at 10:38