HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are there any optimization problems in P whose decision version is hard?

Submitted by: @import:stackexchange-cs··
0
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.