3
$\begingroup$

There seems to usually be a tight connection between decision problems and (corresponding) optimization problems in general. However, is this always the case?

Are there examples where the typical "tight coupling" between a decision problem and the correponding optimization problem breaks down or behaves in an unusual way, e.g. have significantly different complexity?

Or, maybe there is a case where there is a cluster of problems that are all closely related, but the "best" or "definitive" version is not obvious or apparent? Also, I am looking for any survey or broad overview or discussion of this apparent basic connection between decision and optimization problems.

A similar question was asked here, but the answers were highly theoretical and it did not seem to yield any specific or tangible examples.

$\endgroup$
  • $\begingroup$ musing: maybe baker-gill-solovay 1975 P=?NP oracle result could fit into this somehow? other oracle problems? etc $\endgroup$ – vzn Dec 3 '13 at 17:21
  • 4
    $\begingroup$ How about 2-SAT and MAX-2-SAT? We can decide 2-SAT in polynomial time ("is there a satisfying assignment?"), but MAX-2-SAT is NP-hard ("maximize the number of clauses satisfied"). I don't think this is what you want, so you should be careful with definitions: how is this question different from the one you link to? $\endgroup$ – Juho Dec 3 '13 at 17:25
  • $\begingroup$ @Juho I think he means that for a particular NP-complete problem, the decision problem with a positive answer has a proof that can be verified in polynomial time - this "proof" is a the solution to the optimization version of that problem. His question is, I think, if there are any problems for which "the optimization version" has an non-trivial relationship with the "decision version" of the problem (for most problems the relationship is simple, ex. for TSP, "is there a tour of size $k$"=>"show me a tour of size $k$", or UHC: "is there a cycle of size $k$"=>"show me a cycle of size $k$"). $\endgroup$ – Realz Slaw Dec 3 '13 at 17:47
  • 2
    $\begingroup$ I think that the answer depends on what the "corresponding optimization problem" is. For any decision problem, there can be optimization problems which are in $\mathcal{P}$ and others that are in $\mathcal{NP}$. Example: take the decision problem "is there a path from $s$ to $t$ in graph $G$?", then you can associate the optimization problems "find a shortest $s$-$t$-path" and "find a longest $s$-$t$-path". $\endgroup$ – G. Bach Dec 3 '13 at 19:05
  • $\begingroup$ @g think thats an ok example also, will upvote it. it shows that "corresponding optimization problem" is not always totally obvious or automatic. $\endgroup$ – vzn Dec 3 '13 at 19:18
4
$\begingroup$

The answer does indeed depend on how you define a "corresponding" problem.

For example, it is well known 2-SAT is easy ("Given a 2-SAT formula, is it satisfiable?"). However, the optimization problem MAX-2-SAT ("Given a 2-SAT formula, find an assignment maximizing the number of clauses") is NP-hard. Even MIN-2-SAT is NP-hard.

For a given decision problem, you can have "corresponding" optimization problems which are either easy or hard, depending on whether we consider a minimization or a maximization problem. The st-connectivity problem is mentioned in the comments: deciding the existence of such a path is easy, finding a shortest st-path is easy, but finding a longest st-path is hard. Another graph theoretic example is with cuts: computing a minimum cut is easy, but computing a maximum cut is again hard.

You also have decision problems that don't have a corresponding optimization problem, such as primality testing.

$\endgroup$

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.