Editing Subset sum problem (section)

== Pseudo-polynomial time dynamic programming solutions ==

SSP can be solved in [[pseudo-polynomial time]] using [[dynamic programming]]. Suppose we have the following sequence of elements in an instance:

:<math>x_1,\ldots, x_N</math>

We define a ''state'' as a pair (''i'', ''s'') of integers. This state represents the fact that

:"there is a nonempty subset of <math>x_1,\ldots, x_i</math> which sums to {{mvar|s}}."

Each state (''i'', ''s'') has two next states:

* (''i''+1, ''s''), implying that <math>x_{i+1}</math> is not included in the subset;
* (''i''+1, ''s''+<math>x_{i+1}</math>), implying that <math>x_{i+1}</math> is included in the subset.

Starting from the initial state (0, 0), it is possible to use any graph search algorithm (e.g. [[Breadth-first search|BFS]]) to search the state (''N'', ''T''). If the state is found, then by backtracking we can find a subset with a sum of exactly ''T''.

The run-time of this algorithm is at most linear in the number of states. The number of states is at most ''N'' times the number of different possible sums. Let {{mvar|A}} be the sum of the negative values and {{mvar|B}} the sum of the positive values; the number of different possible sums is at most ''B''-''A'', so the total runtime is in <math>O(N(B-A))</math>. For example, if all input values are positive and bounded by some constant ''C'', then ''B'' is at most ''N C'', so the time required is <math>O(N^{2}C)</math>.

This solution does not count as polynomial time in complexity theory because <math>B-A</math> is not polynomial in the ''size'' of the problem, which is the number of bits used to represent it. This algorithm is polynomial in the values of {{mvar|A}} and {{mvar|B}}, which are exponential in their numbers of bits. However, Subset Sum encoded in ''unary'' is in P, since then the size of the encoding is linear in B-A. Hence, Subset Sum is only ''weakly'' NP-Complete.

For the case that each <math>x_i</math> is positive and bounded by a fixed constant {{mvar|C}}, in 1999, Pisinger found a linear time algorithm having time complexity <math>O(NC)</math> (note that this is for the version of the problem where the target sum is not necessarily zero, as otherwise the problem would be trivial).<ref name="Pisinger09">{{cite journal | last = Pisinger | first = David | doi = 10.1006/jagm.1999.1034 | issue = 1 | journal = Journal of Algorithms | mr = 1712690 | pages = 1–14 | title = Linear time algorithms for knapsack problems with bounded weights | volume = 33 | year = 1999}}</ref> In 2015, Koiliaris and Xu found a deterministic <math>\tilde{O}(T \sqrt N)</math> algorithm for the subset sum problem where {{mvar|T}} is the sum we need to find.<ref>{{Cite arXiv|title = A Faster Pseudopolynomial Time Algorithm for Subset Sum |eprint = 1507.02318 |date = 2015-07-08|first1 = Konstantinos|last1 = Koiliaris|first2 = Chao|last2 = Xu|class = cs.DS }}</ref> In 2017, Bringmann found a randomized <math>\tilde{O}(T+N)</math> time algorithm.<ref>{{cite conference | last = Bringmann | first = Karl | editor-last = Klein | editor-first = Philip N. | arxiv = 1610.04712 | contribution = A near-linear pseudopolynomial time algorithm for subset sum | doi = 10.1137/1.9781611974782.69 | pages = 1073–1084 | publisher = SIAM | title = Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) | year = 2017}}</ref>

In 2014, Curtis and Sanches found a simple recursion highly scalable in [[SIMD]] machines having <math>O(N(m-x_{\min})/p)</math> time and <math>O(N+m-x_{\min})</math> space, where {{mvar|p}} is the number of processing elements, <math>m=\min(s, \sum x_i - s)</math> and <math>x_{\min}</math> is the lowest integer.<ref>{{cite journal |last1=Curtis |first1=V. V. |last2=Sanches |first2=C. A. A. |title=An efficient solution to the subset-sum problem on GPU: An efficient solution to the subset-sum problem on GPU |journal=Concurrency and Computation: Practice and Experience |date=January 2016 |volume=28 |issue=1 |pages=95–113 |doi=10.1002/cpe.3636|s2cid=20927927 }}</ref> This is the best theoretical parallel complexity known so far.

A comparison of practical results and the solution of hard instances of the SSP is discussed by Curtis and Sanches.<ref>{{cite journal |last1=Curtis |first1=V. V. |last2=Sanches |first2=C. A. A. |title=A low-space algorithm for the subset-sum problem on GPU |journal=Computers & Operations Research |date=July 2017 |volume=83 |pages=120–124 |doi=10.1016/j.cor.2017.02.006}}</ref>