"NP-complete" optimization problems

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?

Answer 1

An attempt on a partial answer:

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

You have to be careful when carrying over the concepts from decision problems. It can be done and a precise notion of NP-completeness for optimization problems can be given. Look at this answer. It is of course different from the NP-completeness 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 with a feasible solution, 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 by the size of the inputs.
• We can verify efficiently if a solution is a feasible solution of the input.
• 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 also optimal, I would say that this is as hard as solving the original optimization problem because, in order 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.

Answer 2

For the relation between decision and optimization (search) problems, take a peek at Bellare and Goldwasser's The Complexity of Decision versus Search, SIAM Journal of Computing 23(1), feb 1994. In a nutshell: If the decision problem is NP-complete, the search problem is hard too, and can be solved calling the decision problem's solver a polynomial number of times.

Answer 3

You need to look at every individual optimisation problem. Typically you want a “solution” which maximises the value v, while a decision problem would be “is there a solution with a value >= k”

The question is: if you can solve the decision problem, repeatedly, does that allow you to solve the optimisation problem? Usually it lets you solve “what is the maximum value of any solution” using binary search. The difficult part is finding a solution when all you know is that there is a solution.

Answer 4

You can easily define NP-hard optimisation problems: We call a decision problem D NP-hard if any decision problem in NP can be reduced to D in polynomial time. And we can use the same definition for any problem P: P is NP-hard if any decision problem in NP can be reduced to P in polynomial time.

The problem is defining something analogous to NP. If we have a problem “What is the smallest possible value of v”. This is equivalent to asking “is there a solution with a value v” and “is there no solution with a value v-1”. So we can see many optimisation problems as a combination of a problem in NP, and a problem in co-NP.

Answer 5

The reason most optimization problems can be classed as P, NP, NP-complete, etc., is the Kuhn-Tucker conditions. I'll talk in terms of linear-programming problems, but the KTC apply in many other optimization problems. For each optimization problem there is a dual. If the goal in the original problem is to maximize some function, then the dual (usually) has a function to be minimized.* Feasible, but non-optimal solutions to the original problem will be infeasible/invalid for the dual problem, and vice-versa. If, and only if, a solution is feasible for the primary and dual, it is an optimal solution for both. (Technically, may be one of a large number of optimal solutions which give the same result.)

So finding an optimal solution of an optimization problem is equivalent to finding a valid solution for the primary and dual. You may use optimization algorithms to find that solution, but the overall process is an existence proof.

• If you want to flip from minimization to maximization, multiply the objective function by -1.