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.
considered parametrized by the maximum bin size @math and obtained algorithm running in time @math . Subsequently, showed that one can get a faster algorithm for than meet-in-the-middle if @math or @math . MM: derivation of their ideas?: KW done In this paper, we use the hash function that is based on their ideas. Moreover, the ideas in @cite_20 @cite_8 were used in the recent breakthrough polynomial space algorithm @cite_25 running in @math time.
@cite_25 @cite_20 @cite_8
2626471773 1847405718 2963053963
We present randomized algorithms that solve Subset Sum and Knapsack instances with n items in O*(20.86n) time, where the O*(·) notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve Binary Linear Programming on n variables with few constraints in a similar running time. We also show that for any constant k≥ 2, random instances of k-Sum can be solved using O(nk-0.5(n)) time and O(logn) space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(logn) space significantly faster than the trivial O(n2) time algorithm if no value occurs too often in the same list. We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers a ... The SUBSET SUM problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O^*(2^ n 2 )-time algorithm for SUBSET SUM by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O^*(2^ (0.5-delta)*n )-time algorithm, with some constant delta > 0. Continuing an earlier work [STACS 2015], we study SUBSET SUM parameterized by the maximum bin size beta, defined as the largest number of subsets of the n input integers that yield the same sum. For every epsilon > 0 we give a truly faster algorithm for instances with beta = 2^ 0.661n . Consequently, we also obtain a characterization in terms of the popular density parameter n log_2(t): if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for SUBSET SUM and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.