Can the optimization version of a problem be NP-hard while its decision version is in P?

Question

I have formulated an instance of a 0-1 Integer Program (IP), which I am trying to determine the complexity of (can this instance be solved in polynomial time or not). As we know, the 0-1 IP is NP-complete, but I suspect my instance can be solved in polynomial time; which of course does not contradict the hardness of the general 0-1 IP.

Given are a set of variables $S = \{s_0, \dots, s_n\}$, a set of values $V = \{v_0, \dots, v_m\}$, a set of costs $C = \{c_0, \dots, c_m\}$ (where each $v_j, c_j \in \mathbb{Z^+}$), and a positive integer $K$. Assume the values in $V$ and costs in $C$ are sorted, so that the last value in $V$ is the highest, and has the highest corresponding cost.

The optimization version of this problem asks which assignment of $v_j$ to $s_i$ has the lowest cost, where the sum is at least $K$? In addition, each $s \in S$ can only hold one $v \in V$.

To formulate this as a 0-1 IP, we construct a set of binary decision variables. Let this set be $X=\{x_{00},x_{01}, \dots, x_{0m}, \dots, x_{nm}\}$, where $x_k \in \{0, 1\}$ denotes if $v_j$ has been assigned to $s_i$. We then get the constraints:

$$\sum_{j=0}^{m}x_{ij} \leq 1 \quad \forall i=0,1,\dots,n$$ where the last constraint makes sure the sum is at least $K$: $$\sum_{j=0}^{m}x_{ij}v_j \geq K \quad \forall i=0,1,\dots,n$$ The 0-1 IP can then be formulated in its canonical form as: \begin{align} &\text{min} & & c^Tx \\ &\text{s.t} & & Ax \leq b \\ & & & x \geq 0 \end{align} Note that in this represntation, $C$ and $X$ are denoted $c$ and $x$ as they are vectors.

The decision version of this problem asks wether there exists a solution which satisfies $Ax \leq b$. This can be done in polynomial time by setting $x_{im} = 1 \quad \forall i = 0,1,\dots, n$, i.e., every $s \in S$ is assigned the highest value. If the sum of these values are at least $K$, then the answer is "yes", i.e., there is a solution which satisfies $Ax \leq b$. If "no", then there is no solution, because the highest possible sum has been tested.

My question: Since the decision problem can be solved in polynomial time, does it imply that the optimization problem also can be solved in polynomial time? For instance, if the size of $S$ is large, there may be trillions of solutions that satisfy $Ax \leq b$. My knowledge regarding how optimization algorithms work is limited, but as far as I understand, the solution space is 'fixed', so an algorithm would 'only' have to compare the solutions against each other to find the optimal one.

Lastly, I did not use the set $C$ in my decision question. Therefore I am not 100% certain that it is the 'correct' formulation.

I have also read the follwing stackexchange posts:

• Are there any optimization problems in P whose decision version is hard?
• Optimization version of decision problems
• Can the decision version of an optimization problem in NP, be in P?
• If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?

Answer 1

Lastly, I did not use the set $𝐶$ in my decision question. Therefore I am not 100% certain that it is the 'correct' formulation.

It is not correct, indeed :)

You are describing a decision problem, but it does not correspond to your optimization problem. One of the questions you posted (Optimization version of decision problems) explains that quite nicely. Quoting the shortest path example from there:

optimization/search version: Given an undirected unweighted graph $𝐺=(𝑉,𝐸)$ and two vertices $𝑣,𝑢∈𝑉$ , find a shortest path between $𝑣$ and $𝑢$ .

decision version: Given an undirected unweighted graph $𝐺=(𝑉,𝐸)$ , two vertices $𝑣,𝑢∈𝑉$ , and a non-negative integer $𝑘$ , is there a path in $𝐺$ between $𝑢$ and $𝑣$ whose length is at most 𝑘

The emphasized part is what you are missing. The corresponding decision problem is not about finding any solution for the optimization problem. Instead, it is about finding a solution that is at least as good as $𝑘$ for some constant $𝑘$.

So, in your example, you should replace this sentence

The decision version of this problem asks wether there exists a solution which satisfies $𝐴𝑥≤𝑏$ .

with this

The decision version of this problem asks wether there exists a solution which satisfies $𝑐^𝑇𝑥≤k$ (and, of course, still satisfies $𝐴𝑥≤𝑏$) .

to get the correct corresponding decision problem.

Now, if the decision problem is in $P$, you can invoke its polynomial algorithm several times for increasing $k$ and in a binary search manner you will find the answer for the corresponding optimization problem. So, you solved that in polynomial time, too.

Answer 2

Often, if the decision problem can be solved in polynomial time, the optimization problem can be solved in polynomial time as well. For example, if you could decide in polynomial time if a problem has a solution with at most a certain cost, you may be able to binary search for the minimal possible cost.

Your decision problem, however, does not have any restrictions on the cost, and can therefore not be exploited to solve the optimization problem in polynomial time. (In fact, your optimization problem is NP-hard as it can be reduced from the unbounded knapsack problem.)