Editing Subset sum problem (section)

== Computational hardness ==

The [[run-time complexity]] of SSP depends on two parameters: 

* {{nobold|''n''}} - the number of input integers. If ''n'' is a small fixed number, then an [[exhaustive search]] for the solution is practical.
* {{nobold|''L''}} - the precision of the problem, stated as the number of binary place values that it takes to state the problem. If ''L'' is a small fixed number, then there are [[dynamic programming]] algorithms that can solve it exactly.

As both ''n'' and ''L'' grow large, SSP is NP-hard. The complexity of the best known algorithms is [[Exponential time|exponential]] in the smaller of the two parameters ''n'' and ''L''. The problem is NP-hard even when all input integers are positive  (and the target-sum ''T'' is a part of the input). This can be proved by a direct reduction from [[3SAT]].<ref>{{Cite web |last=Goodrich |first=Michael |title=More NP complete and NP hard problems |url=https://www.ics.uci.edu/~goodrich/teach/cs162/notes/pnp3.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.ics.uci.edu/~goodrich/teach/cs162/notes/pnp3.pdf |archive-date=2022-10-09 |url-status=live}}</ref> It can also be proved by reduction from [[3-dimensional matching]] (3DM):<ref name="garey79">{{Garey-Johnson}}, Section&nbsp;3.1 and problem&nbsp;SP1 in Appendix&nbsp;A.3.1.</ref>

* We are given an instance of 3DM, where the vertex sets are W, X, Y. Each set has ''n'' vertices. There are ''m'' edges, where each edge contains exactly one vertex from each of W, X, Y.  Denote ''L'' := ceiling(log<sub>2</sub>(''m''+1)), so that ''L'' is larger than the number of bits required to represent the number of edges.
* We construct an instance of SSP with ''m'' positive integers. The integers are described by their binary representation. Each input integer can be represented by 3''nL'' bits, divided into 3''n'' zones of ''L'' bits. Each zone corresponds to a vertex.
* For each edge (w,x,y) in the 3DM instance, there is an integer in the SSP instance, in which exactly three bits are "1": the least-significant bits in the zones of the vertices w, x, and y. For example, if ''n''=10 and L=3, and W=(0,...,9), X=(10,...,19), Y=(20,...,29), then the edge (0, 10, 20) is represented by the number (2<sup>0</sup>+2<sup>30</sup>+2<sup>60</sup>).
* The target sum ''T'' in the SSP instance is set to an integer with "1" in the least-significant bit of every zone, that is, (2<sup>0</sup>+2<sup>1</sup>+...+2<sup>3n-1</sup>).
* If the 3DM instance has a perfect matching, then summing the corresponding integers in the SSP instance yields exactly T.
* Conversely, if the SSP instance has a subset with sum exactly T, then, since the zones are sufficiently large so that there are no "carries" from one zone to the next, the sum must correspond to a perfect matching in the 3DM instance.

The following variants are also known to be NP-hard:

* The input integers can be both positive and negative, and the target-sum ''T'' = 0. This can be proved by reduction from the variant with positive integers. Denote that variant by SubsetSumPositive and the current variant by SubsetSumZero.  Given an instance (''S'', ''T'') of SubsetSumPositive, construct an instance of SubsetSumZero by adding a single element with value &minus;''T''.  Given a solution to the SubsetSumPositive instance, adding the &minus;''T'' yields a solution to the SubsetSumZero instance. Conversely, given a solution to the SubsetSumZero instance, it must contain the &minus;''T'' (since all integers in S are positive), so to get a sum of zero, it must also contain a subset of S with a sum of +''T'', which is a solution of the SubsetSumPositive instance.
*The input integers are positive, and ''T'' = sum(''S'')/2. This can also be proved by reduction from the general variant; see [[partition problem]].

The analogous counting problem #SSP, which asks to enumerate the number of subsets summing to the target, is [[Sharp P complete|#P-complete]].<ref>[[Yuval Filmus|Filmus, Yuval]] (30 January 2016).  [https://cs.stackexchange.com/a/52466 Answer] to: "[https://cs.stackexchange.com/q/52453 Is there a known, fast algorithm for counting all subsets that sum to below a certain number?]".  ''Theoretical Computer Science [[Stack Exchange]].''  Note that Filmus' citation in support of the claim (Faliszewski, Piotr; Hemaspaandra, Lane (2009). "The complexity of power-index comparison".  ''Theoretical Computer Science''.  Elsevier.  '''410''': 101-107.  DOI&nbsp;[http://dx.doi.org/10.1016/j.tcs.2008.09.034 10.1016/j.tcs.2008.09.034]) does not in fact prove the claim, instead directing readers to another citation ([[Christos Papadimitriou|Papadimitriou, Christos]] (1994). [https://archive.org/details/computationalcom0000papa/ ''Computational Complexity''].  Addison-Wesley: Reading, MA.  Chapter&nbsp;9.  {{ISBN|0-201-53082-1}}&nbsp;&mdash; via the [[Internet Archive]]), which does not explicitly prove the claim either.  Papadimitriou's proof that SSP is NP-complete via reduction of [[3SAT]] does, however, generalize to a reduction from [[Sharp-SAT|#3SAT]] to #SSP.</ref>