If you want to make money online : Register now

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

, , No Comments
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?

Asked By : 1-approximation

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

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback