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

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?

• What is $f$? And in general, the set of NP-hard languages is not closed under taking subsets. – G. Bach Feb 27 '16 at 18:57
• If $B$ is small enough, all you have to do is check a single vector $y_n$, – vonbrand Feb 27 '16 at 20:10
• Can I reduce $(P)'$ to $(P)$? Or are you saying if $B$ is small enough than $(P)$ is easy? – 1-approximation Feb 27 '16 at 20:12
• @G.Bach $f$ is a function from $\mathbb{R}_+$ to $\mathbb{R}_+$ that is monotonically increasing. Unfortunately, I cannot write it explicitly. The two problems $(P)$ and $(P)'$ have the same function $f$, exactly the same. I tried to reduce $(P)'$ to $(P)$ by setting $K=N,a_i=b_i$ but what is the value of $B$ that I should choose? I can't find it. – 1-approximation Feb 27 '16 at 20:19
• Please edit the question to include all relevant information (including the function $f$). Don't just leave information in comments -- we want you to edit the question so it is self-contained. People shouldn't have to read the comments to understand what you are asking. The question does not seem answerable without knowing what $f$ is. Is $f$ fixed? Are you claiming that the first problem is NP-hard for all $f$? I doubt that. So, it seems quite clear that the answer must depend on $f$... which means you need to provide it in the question to make the question well-specified. – D.W. Feb 27 '16 at 23:08

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.
• Thanks. So I cannot say anything about $(P)$? For example, since from every $A$ I cannot find a $B$, then $(P)$ is not NP-hard. Is this fact true? – 1-approximation Feb 27 '16 at 21:45