patternMinor
Are there any optimization problems in P whose decision version is hard?
Viewed 0 times
whoseareversionanyhardproblemsoptimizationdecisionthere
Problem
Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any optimization problem which is easy but its decision version is hard?
Solution
No. The optimization problem is "How big is the biggest $X$?" and the decision problem is "Is there an $X$ that is bigger than $y$?" Solving the decision problem simply involves comparing $y$ with the size of the biggest $X$. You can certainly compare two numbers in polynomial time so, if you can solve the optimization problem (compute the size of the biggest $X$) in polynomial time, you can solve the decision problem.
Context
StackExchange Computer Science Q#91501, answer score: 8
Revisions (0)
No revisions yet.