2
$\begingroup$

It is well known that a optimization problem can be turned into a decision problem with an extra parameter: e.g. in TSP we are looking for the lowest cost for a tour, the decision version therefore could check whether a a tour exists which costs at most $K$.

Lets assume we are talking about an optimization problem which is either NP or NP-hard. Can the corresponding decision problem ever be in P?

NB: What I am trying to ask is: if a optimization problem cannot be solved in polynomial time, can the corresponding decision problem be solve in polynomial time?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Optimization problems cannot belong to NP or be NP-hard any more than apples. NP is a class of decision problems, and NP-hardness is a property of decision problems. When we say that an optimization problem is in NP or is NP-hard, what we really mean is that the corresponding decision problem is in NP or is NP-hard.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ You're right about optimization problems not being in NP, but NP-hard does not only contain decision problems but also optimization problems. Anyway what I want to ask is: if a optimization problem cannot be solved in polynomial time, can the corresponding decision problem be solve in polynomial time? $\endgroup$
    – Héctor van den Boorn
    Apr 26, 2016 at 12:00
  • $\begingroup$ No, actually I'm right about NP-hardness as well. $\endgroup$
    – Yuval Filmus
    Apr 26, 2016 at 12:03
  • $\begingroup$ The more interesting direction is the other one: if the decision version is in P, can we solve the original version in polynomial time? This is the case if, for example, the optimal value is a polynomial-size integer, and the idea is to use binary search (details left to you). $\endgroup$
    – Yuval Filmus
    Apr 26, 2016 at 12:05
  • 2
    $\begingroup$ @YuvalFilmus To be fair, NP-hardness is sometimes used in the context of optimization problems, e.g. wikipedia: "It does not restrict the class NP-hard to decision problems, for instance it also includes search problems, or optimization problems." $\endgroup$
    – Tom van der Zanden
    Apr 26, 2016 at 12:07
  • $\begingroup$ @Tom The same is true for NP. For example, when we say that Max Clique is an NP-complete problem, we are implying that the optimization problem Max Clique is in NP. What we really mean is that the decision version of Max Clique is in NP. Therefore, by definition, if an optimization problem is in NP (or NP-hard) then its decision version is in NP (or NP-hard). $\endgroup$
    – Yuval Filmus
    Apr 26, 2016 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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