22
$\begingroup$

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?

$\endgroup$

migrated from stackoverflow.com Apr 2 '12 at 4:45

This question came from our site for professional and enthusiast programmers.

  • 3
    $\begingroup$ check this question $\endgroup$ – Ran G. Apr 2 '12 at 4:47
  • 1
    $\begingroup$ Also this question: Optimization version of decision problems. $\endgroup$ – Kaveh Apr 2 '12 at 5:10
  • 1
    $\begingroup$ @RanG., I am not sure if this is an exact duplicate. $\endgroup$ – Kaveh Apr 2 '12 at 5:11
  • $\begingroup$ @Kaveh you're right, but the great answer of uli fully answers this question. $\endgroup$ – Ran G. Apr 2 '12 at 5:16
  • $\begingroup$ @RanG., there can be more than one great answers. :) $\endgroup$ – Kaveh Apr 2 '12 at 5:17
13
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.
$\endgroup$
  • 2
    $\begingroup$ I don't see how the KKT conditions relate to NP-hardness, could you elaborate on that? $\endgroup$ – Discrete lizard May 3 '18 at 21:41
  • 2
    $\begingroup$ I don't really see how this answers the question. P, NP, etc., are classes of decision problems. Optimization problems aren't decision problems, so they're not in any of those classes by definition. $\endgroup$ – David Richerby May 4 '18 at 16:10
  • 2
    $\begingroup$ I don't see how this answers the question, either -- this is an interesting comment, but it seems to answer a different question than the one that was asked. The question asks what it means to say that an optimization problem is NP-complete and whether optimization problems can be said to be in NP, given that they aren't a decision problem. This describes how, given an optimization problem (where solutions aren't verifiable), we can often construct a corresponding problem where solutions can be verified. Very interesting stuff, but I'm not sure it answers the question that was asked. $\endgroup$ – D.W. May 4 '18 at 17:03
  • 1
    $\begingroup$ @D.W. The main reason why I think this isn't really answering the question is that, in addition from what was already mentioned, KKT limits the setting to mathematical optimisation of 'regular' (e.g. continuous, differentiable, convex) functions. This setting is inapplicable to most NP-hard problems. $\endgroup$ – Discrete lizard May 5 '18 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.