Can the decision version of an optimization problem in NP, be in P? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:03:56Z https://cs.stackexchange.com/feeds/question/56518 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/56518 2 Can the decision version of an optimization problem in NP, be in P? Héctor van den Boorn https://cs.stackexchange.com/users/50209 2016-04-26T11:45:39Z 2016-04-26T12:00:52Z <p>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\$.</p> <p>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?</p> <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?</p> https://cs.stackexchange.com/questions/56518/-/56520#56520 3 Answer by Yuval Filmus for Can the decision version of an optimization problem in NP, be in P? Yuval Filmus https://cs.stackexchange.com/users/683 2016-04-26T11:57:42Z 2016-04-26T11:57:42Z <p>Optimization problems cannot belong to NP or be NP-hard any more than apples. NP is a class of <em>decision problems</em>, and NP-hardness is a property of <em>decision problems</em>. When we say that an optimization problem is in NP or is NP-hard, what we really mean is that the <em>corresponding decision problem</em> is in NP or is NP-hard.</p>