Equal-subset-sum faster than the meet-in-the-middle. (English) Zbl 07525510
Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 73, 16 p. (2019).
Summary: In the Equal-Subset-Sum problem, we are given a set \(S\) of \(n\) integers and the problem is to decide if there exist two disjoint nonempty subsets \(A,B\subseteq S\), whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in \(\mathcal{O}^*(3^{n/2})\le\mathcal{O}^*(1.7321^n)\) time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give \(\mathcal{O}^*(1.7088^n)\) worst case Monte Carlo algorithm. This answers a question suggested by Woeginger in his inspirational survey.
Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in \(\mathcal{O}^*(3^n)\) time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in \(\mathcal{O}^*(2.6817^n)\) time and polynomial space.
For the entire collection see [Zbl 1423.68016].
Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in \(\mathcal{O}^*(3^n)\) time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in \(\mathcal{O}^*(2.6817^n)\) time and polynomial space.
For the entire collection see [Zbl 1423.68016].
MSC:
| 68Wxx | Algorithms in computer science |
Keywords:
equal-subset-sum; subset-sum; meet-in-the-middle; enumeration technique; randomized algorithmOnline Encyclopedia of Integer Sequences:
Least k such that there is a set S in {1, 2, ..., k} with n elements and the property that each of its subsets has a distinct sum.References:
| [1] | Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 41-57. SIAM, 2019. · Zbl 1431.68040 |
| [2] | Per Austrin, Petteri Kaski, Mikko Koivisto, and Jussi Määttä. Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming -40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 45-56. Springer, 2013. · Zbl 1336.68320 |
| [3] | Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Subset Sum in the Absence of Concentration. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 48-61. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2015. · Zbl 1355.68109 |
| [4] | Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Dense Subset Sum May Be the Hardest. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 13:1-13:14. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2016. · Zbl 1388.68079 |
| [5] | Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, and Aviad Rubinstein. Reductions in PPP. Inf. Process. Lett., 145:48-52, 2019. 73:14 Equal-Subset-Sum Faster Than the Meet-in-the-Middle · Zbl 1446.68067 |
| [6] | Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas. Faster space-efficient algorithms for subset sum and k-sum. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 198-209. ACM, 2017. · Zbl 1369.68348 |
| [7] | Cristina Bazgan, Miklos Santha, and Zs. Tuza. Efficient approximation algorithms for the Subset-Sums Equality problem. In International Colloquium on Automata, Languages, and Programming, pages 387-396. Springer, 1998. · Zbl 0914.90223 |
| [8] | Paul Beame, Raphaël Clifford, and Widad Machmouchi. Element Distinctness, Frequency Moments, and Sliding Windows. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 290-299. IEEE Computer Society, 2013. |
| [9] | Anja Becker, Jean-Sébastien Coron, and Antoine Joux. Improved Generic Algorithms for Hard Knapsacks. In Kenneth G. Paterson, editor, Advances in Cryptology -EUROCRYPT 2011 -30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings, volume 6632 of Lecture Notes in Computer Science, pages 364-385. Springer, 2011. · Zbl 1281.94014 |
| [10] | Tom Bohman. A sum packing problem of Erdős and the Conway-Guy sequence. Proceedings of the American Mathematical Society, 124(12):3627-3636, 1996. · Zbl 0874.11027 |
| [11] | Karl Bringmann. A Near-linear Pseudopolynomial Time Algorithm for Subset Sum. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pages 1073-1084, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. · Zbl 1423.90210 |
| [12] | Mark Cieliebak. Algorithms and hardness results for DNA physical mapping, protein identific-ation, and related combinatorial problems. PhD thesis, ETH Zürich, 2003. |
| [13] | Mark Cieliebak, Stephan Eidenbenz, and Aris Pagourtzis. Composing equipotent teams. In International Symposium on Fundamentals of Computation Theory, pages 98-108. Springer, 2003. · Zbl 1278.68104 |
| [14] | Mark Cieliebak, Stephan Eidenbenz, Aris Pagourtzis, and Konrad Schlude. On the Complexity of Variations of Equal Sum Subsets. Nord. J. Comput., 14(3):151-172, 2008. · Zbl 1187.68248 |
| [15] | Mark Cieliebak, Stephan Eidenbenz, and Paolo Penna. Noisy data make the partial digest problem NP-hard. In International Workshop on Algorithms in Bioinformatics, pages 111-123. Springer, 2003. |
| [16] | John H Conway and Richard K Guy. Sets of natural numbers with distinct subset sums. Notices Amer. Math. Soc, 15:345, 1968. |
| [17] | Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus-Peter Schnorr, and Jacques Stern. Improved Low-Density Subset Sum Algorithms. Computational Complexity, 2:111-128, 1992. · Zbl 0768.11049 |
| [18] | Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On Problems as Hard as CNF-SAT. In Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012, pages 74-84. IEEE Computer Society, 2012. |
| [19] | Paul Erdős. Problems and results in additive number theory. Journal London Wash. Soc, 16:212-215, 1941. · JFM 67.0984.03 |
| [20] | Paul Erdős. A survey of problems in combinatorial number theory. Annals of Discrete Mathematics, 6:89-115, 1980. · Zbl 0448.10002 |
| [21] | Godfrey Harold Hardy, Edward Maitland Wright, et al. An introduction to the theory of numbers. Oxford university press, 1979. · Zbl 0423.10001 |
| [22] | Danny Harnik and Moni Naor. On the Compressibility of NP Instances and Cryptographic Applications. SIAM J. Comput., 39(5):1667-1713, 2010. · Zbl 1207.68162 |
| [23] | Rebecca Hoberg, Harishchandra Ramadas, Thomas Rothvoss, and Xin Yang. Number Bal-ancing is as Hard as Minkowski’s Theorem and Shortest Vector. In Friedrich Eisenbrand and Jochen Könemann, editors, Integer Programming and Combinatorial Optimization -19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, volume 10328 of Lecture Notes in Computer Science, pages 254-266. Springer, 2017. 73:15 · Zbl 1418.90228 |
| [24] | Ellis Horowitz and Sartaj Sahni. Computing Partitions with Applications to the Knapsack Problem. J. ACM, 21(2):277-292, 1974. · Zbl 0329.90046 |
| [25] | Nick Howgrave-Graham and Antoine Joux. New Generic Algorithms for Hard Knapsacks. In Henri Gilbert, editor, Advances in Cryptology -EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 -June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 235-256. Springer, 2010. · Zbl 1280.94069 |
| [26] | Russell Impagliazzo and Moni Naor. Efficient Cryptographic Schemes Provably as Secure as Subset Sum. J. Cryptology, 9(4):199-216, 1996. · Zbl 0862.94015 |
| [27] | Ce Jin and Hongxun Wu. A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum. In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, January 8-9, 2019 -San Diego, CA, USA, volume 69 of OASICS, pages 17:1-17:6. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2019. · Zbl 07902020 |
| [28] | Narendra Karmarkar and Richard M. Karp. An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem. In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 312-320. IEEE Computer Society, 1982. |
| [29] | Konstantinos Koiliaris and Chao Xu. A Faster Pseudopolynomial Time Algorithm for Subset Sum. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pages 1062-1072, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. · Zbl 1422.90046 |
| [30] | Konstantinos Koiliaris and Chao Xu. Subset Sum Made Simple. CoRR, abs/1807.08248, 2018. arXiv:1807.08248. · Zbl 1454.90076 |
| [31] | J. C. Lagarias and Andrew M. Odlyzko. Solving Low-Density Subset Sum Problems. J. ACM, 32(1):229-246, 1985. · Zbl 0632.94007 |
| [32] | Daniel Lokshtanov and Jesper Nederlof. Saving space by algebraization. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 321-330. ACM, 2010. · Zbl 1293.68148 |
| [33] | W Fred Lunnon. Integer sets with distinct subset-sums. Mathematics of Computation, 50(181):297-320, 1988. · Zbl 0654.10016 |
| [34] | Ralph C. Merkle and Martin E. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Trans. Information Theory, 24(5):525-530, 1978. · Zbl 1487.94132 |
| [35] | Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, and Karol Wegrzycki. Equal-Subset-Sum Faster Than the Meet-in-the-Middle. CoRR, abs/1905.02424, 2019. arXiv:1905.02424. |
| [36] | Jesper Nederlof, Erik Jan van Leeuwen, and Ruben van der Zwaan. Reducing a Target Interval to a Few Exact Queries. In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors, Mathematical Foundations of Computer Science 2012 -37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings, volume 7464 of Lecture Notes in Computer Science, pages 718-727. Springer, 2012. · Zbl 1365.68290 |
| [37] | Christos H. Papadimitriou. On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci., 48(3):498-532, 1994. · Zbl 0806.68048 |
| [38] | Herbert Robbins. A remark on Stirling’s formula. The American mathematical monthly, 62(1):26-29, 1955. · Zbl 0068.05404 |
| [39] | Richard Schroeppel and Adi Shamir. A T=O(2 n/2 ). SIAM J. Comput., 10(3):456-464, 1981. · Zbl 0462.68015 |
| [40] | Adi Shamir. A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem. IEEE Trans. Information Theory, 30(5):699-704, 1984. · Zbl 0552.94007 |
| [41] | Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis. PPP-Completeness with Con-nections to Cryptography. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 148-158. IEEE Computer Society, 2018. 73:16 Equal-Subset-Sum Faster Than the Meet-in-the-Middle |
| [42] | David A. Wagner. A Generalized Birthday Problem. In Moti Yung, editor, Advances in Cryptology -CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings, volume 2442 of Lecture Notes in Computer Science, pages 288-303. Springer, 2002. · Zbl 1026.94541 |
| [43] | Gerhard J. Woeginger. Space and Time Complexity of Exact Algorithms: Some Open Problems (Invited Talk). In Rodney G. Downey, Michael R. Fellows, and Frank K. H. A. Dehne, editors, Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings, volume 3162 of Lecture Notes in Computer Science, pages 281-290. Springer, 2004. · Zbl 1104.68520 |
| [44] | Gerhard J. Woeginger. Open problems around exact algorithms. Discrete Applied Mathematics, 156(3):397-405, 2008. · Zbl 1165.90613 |
| [45] | Gerhard J. Woeginger and Zhongliang Yu. On the Equal-Subset-Sum Problem. Inf. Process. Lett., 42(6):299-302, 1992. · Zbl 0772.68059 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
