# “Unusual” coupling between a decision problem and a corresponding optimization problem

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.

• musing: maybe baker-gill-solovay 1975 P=?NP oracle result could fit into this somehow? other oracle problems? etc – vzn Dec 3 '13 at 17:21
• 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? – Juho Dec 3 '13 at 17:25
• @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$"). – Realz Slaw Dec 3 '13 at 17:47
• 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". – G. Bach Dec 3 '13 at 19:05
• @g think thats an ok example also, will upvote it. it shows that "corresponding optimization problem" is not always totally obvious or automatic. – vzn Dec 3 '13 at 19:18