Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
If a decision problem is in P, is the associated optimization problem then also efficiently solvable?
I always thought that this is the case but according to Wikipedia page on Decision Problems the complexity of a decision and function problem might differ and to me a function problem was always a special case of an optimization problem, hence I was under the impression that if the decision problem is efficiently decidable the same applies to the corresponding optimization problem.
Let us consider a generic optimization problem:
Maximize $f(x)$ subject to the constraint $x \in \mathcal{D}$.
The corresponding decision version is
Given $\mathcal{D}$ and $T$, is there $x \in \mathcal{D}$ such that $f(x) \geq T$?
In most cases, the range of $f(x)$ is at most exponential in the description length of $\mathcal{D}$, and so the optimization problem reduces to the decision version via binary search. For example, if $0 \leq f(x) \leq n$, then we first ask whether there is a solution with $f(x) \geq n/2$; depending on the answer, we ask whether there is a solution with $f(x) \geq n/4$ (if the answer was negative) or with $f(x) \geq 3n/4$ (if the answer was positive); and so on.
Conversely, if we can solve the optimization problem then we can easily answer the decision problem, and so the two are essentially equivalent.
Take a peek at Bellare and Goldwasser's The Complexity of Decision versus Search SIAM J. on Computing 23:1 (feb 1994), a version for class use is here. Short answer: If the decision problem is in NP, they are "equivalent" (the optimization problem can be solved using a polynomial number of calls to the decision problem), if the decision problem is harder (and some quite plausible conjectures pan out) they aren't.
Consider the Travelling Salesman Problem (TSP).
Decision Version (DV): Given an undirected weighted graph $G$, does there exist a Hamiltonian cycle of weight at most 'w' in the Graph?
Optimization Version (OV): Given an undirected weighted graph $G$, find the hamiltonian cycle of minimum weight?
Case 1: If P $=$ NP.
Since there is a polynomial-time reduction from DV to OV and vice-versa (link), both the problems are in P. Here, the complexity of both the problems are the same.
Case 2: If P $\neq$ NP
Here, we will show that the complexity of both the problems are different.
Note that the Decision version of TSP is in NP since given a sequence of vertices, we can verify in polynomial time if the sequence is a hamiltonian cycle of weight at most 'w'.
However, for the Optimization version of TSP, how will you know if it belongs to NP. In other words, given a Hamiltonian cycle of 'w', how can you verify if it is the optimal one? As per my thinking, to verify its optimality you must know the optimal solution. Since P $\neq$ NP, we can not find the optimal solution in polynomial time. Therefore, we might not be able to say if TSP is in NP.
Thus, the complexity of Decision Version and Optimization Version could be different.
