So I know the conditions required for a problem to be NP-Complete is that it has to lie within NP and has to be NP-hard.

The given problem I have is subset sum.

However, the conditions have been change to sum ≤ M and sum ≥ M from sum = M. To be more specific:

  1. "If we ask if there is a subset with sum ≤ M, is the problem still NP- Complete?"

  2. "If we ask if there is a subset with sum ≥ M, is the problem still NP- Complete?"

My initial reaction is that the two problems are no longer NP-complete since they can both be solved within polynomial time.

  1. Check each element and see if there exists at least one smaller than M.
  2. Add all positive integers and see if the sum of all elements is larger than M.

Since it isn't NP Hard, it cannot therefore be NP-complete.

Am I thinking/approaching this correctly?

  • 3
    $\begingroup$ If P=NP then any problem in P (other than the empty language and the complete language) is NP-complete. $\endgroup$ – Yuval Filmus May 22 '19 at 15:05
  • $\begingroup$ Unfortunately, "Am I thinking/approaching this correctly?" is not a good fit for our question format (see, e.g., meta discussions meta discussions here and here). You seem to already have proven your version of subset sum is in P. Are there any conceptual questions we could help you with? If so, please include these in the question text. $\endgroup$ – dkaeae May 22 '19 at 15:29
  • $\begingroup$ @dkaeae, I understand what you mean. It is a bad way to ask a question, but I am not looking for an answer. I am seeking confirmation since this is still new for me. I guess the question itself stems from insecurities. $\endgroup$ – red31 May 23 '19 at 9:35
  • $\begingroup$ @red31 If you are not looking for a concrete answer, then this is probably not the right place to ask the question. $\endgroup$ – Discrete lizard May 23 '19 at 16:08

What precisely are the problems? I may be missing something (and cannot do comments yet). Are they

(1) Given a set $A \subseteq \mathbb{Z}$ of $n$ elements, does there exist some subset $S \subseteq A$ with $\sum_{x \in S} x \le M$.

(2) Given a set $ \subseteq \mathbb{Z}$ of $n$ elements, does there exist some subset $S \subseteq A$ with $\sum_{x \in S} x \ge M$.

If so these problems seem clearly in $\mathbf{P}$, basically by the reasoning you described -- we just want the minimum/maximum possible subset sum, and then we compare that with $M$. Assuming empty $S$ is allowed:

  • for (1), add up all the negative numbers in $A$ and see if it's $\le M$. If Yes, then return yes. If not, return No.

  • for (2), add up all the positive numbers in $A$ and see if it's $\ge M$.

Again I may be missing something, but it seems like the other answer's reduction might not be addressing the possibility that $SS_\le$ and $SS_\ge$ would return yes based on different sets? Like consider input $A = \{1, 3\}$ and $M=2$.

| cite | improve this answer | |
  • $\begingroup$ I have updated the question to be more clear. However, I must admit I am probably more confused now then I was before. Especially after the response indicating that it is in fact still NP-Complete. $\endgroup$ – red31 May 23 '19 at 9:34
  • 1
    $\begingroup$ @red31 I don't see any response indicating it is still $NP$-complete. It's just that your reasoning, that being poly-time solvable implies not being $NP$-hard, is incorrect. That reasoning is only valid if $P\not = NP$, something which is likely suspected, but not known to be true. You cannot say the problem is not $NP$-hard, you can only say that it is not $NP$-hard unless $P=NP$. $\endgroup$ – Tom van der Zanden May 23 '19 at 9:56
  • 1
    $\begingroup$ @red31 None. It's impossible to prove it's not NP-complete without proving $P\not = NP$. $\endgroup$ – Tom van der Zanden May 23 '19 at 10:13
  • 1
    $\begingroup$ @red31 ok reading over, yeah your reasoning (and mine) is correct. What's your remaining confusion? The other answer proposed a reduction in which, to solve the $=M$ version, you query the $\le M$ version twice -- once to see if there's a subset with sum $\le M$, and another to see if there's a subset with sum $\ge M$. Those two queries can be done. But the problem is that it's easily possible for there to be a "YES" answer to the $\le M$ version and the $\ge M$ version without a "YES" answer for the $=M$ version. The reduction does no work. See the $\{1, 3\}$ and $M=2$ case for example. $\endgroup$ – xmq May 23 '19 at 22:57
  • 1
    $\begingroup$ @red31 And yeah as Tom said, if $\mathbf{P}$ were to equal $\mathbf{NP}$, then all nontrivial $\mathbf{P}$ languages would be $\mathbf{NP}$-complete. So you need to assume $\mathbf{P} \neq \mathbf{NP}$ to claim that this $\mathbf{P}$ problem is not $\mathbf{NP}$-complete. [ref e.g. cs.stackexchange.com/questions/35128/… ] $\endgroup$ – xmq May 23 '19 at 23:03

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