2 added 31 characters in body
source | link

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?

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)?

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?

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?

1
source | link

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)?

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?