1
$\begingroup$

I'm reading up about the Knapsack problem on Wiki and it's associated problem, the subset sum problem. However, the language is a little vague, so I'd like to clarify about what exactly is going on here.

If I define my problem to be a set of positive integers only, to target a positive integer, is that still an NP-complete problem of the subset-sum/knapsack variant?

1 Answers 1

1

In Sipser's book he gives a nice reduction from 3SAT to Subset Sum which uses only positive numbers, so the problem is still NP-complete.