I am slightly confused by some terminology I have encountered regarding the comp

Question

I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. However, I am not exactly sure what the term NP-complete means in the context of an optimization problem. Does this just mean that the corresponding decision problem is NP-complete? And does that mean that the optimization problem may in fact be harder (perhaps outside of NP)?

In particular, I am concerned about the fact that while an NP-complete decision problem is polynomial time verifiable, a solution to a corresponding optimization problem does not appear to be polynomial time verifiable. Does that mean that the problem is not really in NP, or is polynomial time verifiability only a characteristic of NP decision problems?

Explanation / Answer

An attempt on a partial answer:

Decision problems where already investigated for some time before optimization problems came into view, in the sense as they are treated from the approximation algorithms perspective.

So you have to be careful when carrying over the concepts from decision problems. It can be done and a precise notion of NP-completness for optimization problems can be given. See this answer. It is of course different from the NP-completness for decision problems. But it is based on the sames ideas (reductions).

If you are faced with an optimization problem that doesn

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.