# 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

• 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