and , 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 is positive and bounded by a fixed constant , Pisinger found a linear time algorithm having time complexity (note that this is for the version of the problem where the target sum is not necessarily zero, otherwise the problem would be trivial). In 2015, Koiliaris and Xu found a deterministic algorithm for the subset sum problem where is the sum we need to find. In 2017, Bringmann found a randomized time algorithm. In 2014, Curtis and Sanches found a simple recursion highly scalable in SIMD machines having time and space, where is the number of processing elements, and is the lowest integer. 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. Polynomial time approximation algorithms Suppose all inputs are positive. An approximation algorithm to SSP aims to find a subset of S with a sum of at most T and at least r times the optimal sum, where r is a number in (0,1) called the approximation ratio. Simple 1/2-approximation The following very simple algorithm has an approximation ratio of 1/2: Order the inputs by descending value; Put the next-largest input into the subset, as long as it fits there. When this algorithm terminates, either all inputs are in the subset (which is obviously optimal), or there is an input that does not fit. The first such input is smaller than all previous inputs that are in the subset and the sum of inputs in the subset is more than T/2 otherwise the input also is less than T/2 and it would fit in the set. Such a sum greater than T/2 is obviously more than OPT/2. Fully-polynomial time approximation scheme The following algorithm attains, for every , an approximation ratio of . Its run time is polynomial in and . Recall that n is the number of inputs and T is the upper bound to the subset sum. initialize a list L to contain one element 0. for each i from 1 to n do let Ui be a list containing all elements y in L,