"NP-complete" optimization problems

Problem Detail: 

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?

Asked By : Aniket Schneider

Answered By : uli

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't allow a verification that a solution is feasible then there is not much you can do. That is why one usually assumes, that:

• We can verify efficiently if the input is actually a valid instance of our optimization problem.
• The size of the feasible solutions is bounded polynomially in the size of the inputs.
• We can verify efficiently if a solution is a feasible solution of the input.
• And the value of a solution can be determined efficiently.

Otherwise there is not much we can hope to achieve.

The complexity class $\mathrm{NP}$ only contains decisions problems per definition. So there aren't any optimizations problems in it. And the Verifier-based definition of $\mathrm{NP}$ you mention is specific to $\mathrm{NP}$. I haven't encountered it with optimization problems.

If you want to verify that a solution is not just feasible but optimal. I would say that this is as hard as solving the original optimization problem. Because to refute a given feasible and possibly optimal solution as non-optimal, you have to give a better solution, which might require you to find the true optimal solution.

But that doesn't mean that the optimization problem is harder. See this answer, which depends of course on the precise definitions.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/982