137k views
8 votes
given a set of integers, does any non-empty subset of them add up to zero? That is a decision problem and happens to be NP-complete?

1 Answer

13 votes
no because the subset sum problem is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target sum T, and the question is to decide whether any subset of the integers sum to precisely. the problem is known to be NP-complete. moreover, some restricted variants of it are NP-complete too, for example.
User Gerum
by
3.4k points