0
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user1377493 Nov 9 '16 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.