If you want to make money online : Register now

[Solved]: "Unusual" coupling between a decision problem and a corresponding optimization problem

, , No Comments
Problem Detail: 

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.

Asked By : vzn

Answered By : Juho

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.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback