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?

  • 1
    $\begingroup$ What is $f$? And in general, the set of NP-hard languages is not closed under taking subsets. $\endgroup$
    – G. Bach
    Feb 27 '16 at 18:57
  • $\begingroup$ If $B$ is small enough, all you have to do is check a single vector $y_n$, $\endgroup$
    – vonbrand
    Feb 27 '16 at 20:10
  • $\begingroup$ Can I reduce $(P)'$ to $(P)$? Or are you saying if $B$ is small enough than $(P)$ is easy? $\endgroup$ Feb 27 '16 at 20:12
  • $\begingroup$ @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. $\endgroup$ Feb 27 '16 at 20:19
  • $\begingroup$ 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. $\endgroup$
    – 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.

  • $\begingroup$ 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? $\endgroup$ Feb 27 '16 at 21:45
  • 1
    $\begingroup$ No, definitely not. You can't conclude that P is not NP-hard. It might be NP-hard. But a direct proof by reduction from P' might not be possible. $\endgroup$ Feb 27 '16 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.