If you want to make money online : Register now

# [Answers] Does a problem stay NP-hard when an additional constraint is added to it?

, ,
Problem Detail:

I have the following problem $(P)'$:

\begin{align*} {\rm max}_{x_1,...,x_K}\quad & \sum_{k=1}^Kf(a_k,x_k) \cr & & (P)'\cr {\rm subject\ to}\quad & 0 \le x_k \le A, k=1,\ldots,K. \end{align*}

This problem is proven NP-hard. An instance of $(P)'$ is given by $(K,a_i,A)$.

I have another problem $(P)$:

\begin{align*} {\rm max}_{y_1,...,y_N}\quad & \sum_{n=1}^Nf(b_n, y_n) \cr & & (P)\cr {\rm subject\ to}\quad & 0 \le\sum_{n=1}^Ky_n \le B, \cr \quad & y_n\geq 0, n=1,\ldots,N. \end{align*} And an instance of $(P)$ is given by $(N,b_i,B)$.

Can I say that problem $(P)$ is NP-hard?

#### Answered By : Yuval Filmus

For general $f$ you can't conclude that $P$ is NP-hard just from the fact that $P'$ is NP-hard. In order to do so, you would need to come up with a reduction from $P'$ to $P$. For such a reduction to work, you would need that for every value of $A$ there be a value of $B$ such that the two systems of constraints are equivalent. Unfortunately this is not the case.

###### Best Answer from StackOverflow

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

3.2K people like this