2016/12/08 by Nikhil Bansal, Shashwat Garg, Bansal, Nikhil +5 · 1 voice · 2 citations
Computer Science · Engineering · Mathematics · #Algorithm #Algorithms and Data Compression #Binary logarithm #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Expected value #Knapsack problem #Mathematics #Modulo #Optimization and Packing Problems #Polynomial #Random access #Random variable #Space (punctuation) #Statistics #Time complexity #Value (mathematics) #cs.CC #cs.CR #cs.DS
paper · pdf · doi:10.48550/arxiv.1612.02788
23 pages, 3 figures
openalex publication_date 2016/12/08 · arxiv created 2017/06/24 · arxiv updated 2017/06/27 · openalex created_date 2025/10/24 · openalex updated_date 2026/08/05
We present space efficient Monte Carlo algorithms that solve Subset Sum and Knapsack instances with n items using O^*(20.86n) time and polynomial space, where the O^*(⋅) notation suppresses factors polynomial in the input size. Both algorithms assume random read-only access to random bits. Modulo this mild assumption, this resolves a long-standing open problem in exact algorithms for NP-hard problems. 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.5polylog(n)) time and O(log n) 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(log n) space significantly faster than the trivial O(n2) time algorithm if no value occurs too often in the same list.