In the Equal-Subset-Sum problem, we are given a set @math of @math integers and the problem is to decide if there exist two disjoint nonempty subsets @math , whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in @math time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give @math worst case Monte Carlo algorithm. This answers the open problem from Woeginger's inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in @math time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in @math time and polynomial space.
From the pseudopolynomial algorithms perspective Knapsack and admit @math algorithm, where @math is a value of a target. Recently, for the pseudopolynomial algorithm was improved to run in deterministic @math time by and randomized @math time by (and simplified, see @cite_2 @cite_16 ). However, these algorithms have a drawback of running in pseudopolynomial space @math . Surprisingly, presented an algorithm running in time @math and space @math which was later improved to @math time and @math space assuming the Extended Riemann Hypothesis @cite_21 .
@cite_16 @cite_21 @cite_2
2883642199 2537252502 2885641822
Subset Sum is a classical optimization problem taught to undergraduates as an example of an NP-hard problem, which is amenable to dynamic programming, yielding polynomial running time if the input numbers are relatively small. Formally, given a set @math of @math positive integers and a target integer @math , the Subset Sum problem is to decide if there is a subset of @math that sums up to @math . Dynamic programming yields an algorithm with running time @math . Recently, the authors [SODA '17] improved the running time to @math , and it was further improved to @math by a somewhat involved randomized algorithm by Bringmann [SODA '17], where @math hides polylogarithmic factors. Here, we present a new and significantly simpler algorithm with running time @math . While not the fastest, we believe the new algorithm and analysis are simple enough to be presented in an algorithms class, as a striking example of a divide-and-conquer algorithm that uses FFT to a problem that seems (at first) unrelated. In particular, the algorithm and its analysis can be described in full detail in two pages (see pages 3-5). Given a set Z of n positive integers and a target value t, the S ubset S um problem asks whether any subset of Z sums to t. A textbook pseudopolynomial time algorithm by Bellman from 1957 solves S ubset S um in time O(nt). This has been improved to O(n max Z) by Pisinger [J. Algorithms'99] and recently to [EQUATION] by Koiliaris and Xu [SODA'17]. Here we present a simple and elegant randomized algorithm running in time O(n+t). This improves upon a classic algorithm and is likely to be near-optimal, since it matches conditional lower bounds from S et C over and k-C lique . We then use our new algorithm and additional tricks to improve the best known polynomial space solution from time O(n3t) and space O(n2) to time O(nt) and space O(n log t), assuming the Extended Riemann Hypothesis. Unconditionally, we obtain time O(nt1+e) and space O(nte) for any constant e > 0. Given a multiset S of n positive integers and a target integer t, the Subset Sum problem asks to determine whether there exists a subset of S that sums up to t. The current best deterministic algorithm, by Koiliaris and Xu [SODA'17], runs in O (sqrt n t) time, where O hides poly-logarithm factors. Bringmann [SODA'17] later gave a randomized O (n + t) time algorithm using two-stage color-coding. The O (n+t) running time is believed to be near-optimal. In this paper, we present a simple and elegant randomized algorithm for Subset Sum in O (n + t) time. Our new algorithm actually solves its counting version modulo prime p>t, by manipulating generating functions using FFT.