METHODS AND ALGORITHMS FOR SOLVING THE PROBLEM ON THE SUM OF SUBSETS
DOI:
https://doi.org/10.37943/23AFRZ7022Keywords:
NP-complete class, polynomial solvability, subset sum problem, time, space, complexity theory, big dataAbstract
We study special-case algorithms for the subset-sum problem when the subset size is fixed to , using algebraic and geometric formulations that yield practical procedures with clear time and space bounds. The subset sum problem is one of the fundamental problems in computational complexity theory. It consists of determining whether, given a finite set of non-negative integers, there exists a subset whose sum of elements is equal to a predetermined number. This problem belongs to the class of nondeterministic polynomial time complete (NP-complete) problems: its solution can be verified in polynomial time, but an efficient algorithm for the general case has not yet been found. The goal of our research is to find new methods for solving the subset sum problem for special cases using algebraic and geometric approaches. The proposed method is based on a polynomial formulation of the problem inspired by Waring's conjecture for polynomials and the Neumann–Slater theorem. The main idea is to construct polynomials whose coefficients contain information about the sum of the elements of a subset. Using Vieta's theorem and the Euclidean algorithm, the problem is reduced to checking whether certain algebraic conditions are satisfied. The article proposes two lemmas proving the polynomial solvability of the subset sum problem for subset cardinality two and three. Based on them, two algorithms are developed: one uses value mapping and a fusion method, the other is based on a geometric criterion for collinearity of points obtained by transforming set elements. The algorithms demonstrate efficiency in terms of time and memory and do not require division into verification and decision stages. Effective methods for solving it allow us to develop faster algorithms for intelligent information processing, optimization of computing processes, and construction of reliable data protection systems. Our results establish polynomial-time solvability only for these fixed-???? cases and do not claim consequences for the general subset-sum problem or for the P vs NP question.
References
Sinchev, B., Sinchev, A. B., Akzhanova, J., & Mukhanova, A. M. (2019). New methods of information search. News of the National Academy of Sciences of Kazakhstan, Series of Geology and Technical Sciences, 3(435), 240–246, https://doi.org/10.32014/2019.2518-170X.91.
Bringmann, K. (2017). A near-linear pseudopolynomial time algorithm for subset sum. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) (pp. 1073–1084). SIAM. https://doi.org/10.1137/1.9781611974782.69
Bringmann, K., Nakos, V. (2020) Top-k-convolution and the quest for near-linear output-sensitive subset sum. In: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC 2020, pp 982–995. ACM, New York, https://doi.org/10.1145/3357713.3384308
Aitim, A. and Abdulla, M. (2024) “Data processing and analysing techniques in UX research,” Procedia Computer Science. https://doi:10.1016/j.procs.2024.11.154
Yuan, C., & Yang, H. (2019). Research on K-Value Selection Method of K-Means Clustering Algorithm. J, 2(2), 226-235. https://doi.org/10.3390/j2020016
Khan, MA. (2017) Some problems on graphs and arrangements of convex bodies. PRISM. https://doi.org/10.11575/PRISM/10182
Koiliaris, K., Xu, C. (2019) Faster pseudopolynomial time algorithms for subset sum. ACM Trans Algorithms 15(3):40. https://doi.org/10.1145/3329863
Lahyani, R., Chebil., K, Khemakhem, M., Coelho, LC. (2019) Matheuristics for solving the multiple knapsack problem with setup. Comput Ind Eng 129:76–89. https://doi.org/10.1016/j.cie.2019.01.010
Recalde, D., Severín, D., Torres, R., Vaca, P. (2018) An exact approach for the balanced k-way partitioning problem with weight constraints and its application to sports team realignment. J Comb Optim 36(3):916–936. https://doi.org/10.1007/s10878-018-0254-1
Sinchev, B., Sinchev, A. B., & Akzhanova, Z. A. (2019). Computing network architecture for reducing a computing operation time and memory usage associated with determining, from a set of data elements, a subset of at least two data elements, associated with a target computing operation result // Patent in USPTO, 2019, 1-38.
Schreiber E., Korf R., Moffitt M. (2018) Optimal multi-way number partitioning. J ACM 65(4):24. https://doi.org/10.1145/3184400
Li, H., Ni, P., & Zan, Y. (2023). Public-Key Encryption from Average Hard NP Language. Cryptology ePrint Archive, 2023/1260.
Liu, Y., Pass, R. (2022). On One-way Functions from NP-Complete Problems. In: Proceedings of the 37th Computational Complexity Conference (CCC '22). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU, Article 36, 1–24. https://doi.org/10.4230/LIPIcs.CCC.2022.36
Mukhamedov, F., & Qaralleh, I. (2021). On S-Evolution Algebras and Their Enveloping Algebras. Mathematics, 9(11), 1195. https://doi.org/10.3390/math9111195
Aitim, A., & Satybaldieva, R. (2024). Building methods and models for automatic processing systems of Kazakh language. KazATC Bulletin, 137(2), 346–356. https://doi.org/10.52167/1609-1817-2025-137-2-346-356
Blömer J., Brauer S., Bujna K. 2020. A Complexity Theoretical Study of Fuzzy K-Means. ACM Trans. Algorithms 16, 4, (October 2020), 25 pages. https://doi.org/10.1145/3409385
Hirahara S., Carboni I., and Santhanam R. Np-hardness of minimum circuit size problem for OR-AND-MOD circuits, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pages 5:1-5:31, 2018, https://doi.org/10.4230/LIPIcs.CCC.2018.5.
Salas, J. (2025). Beyond worst-case subset sum: An adaptive, structure-aware solver with sub-2ⁿ⁄² enumeration. arXiv preprint arXiv:2503.20162. https://arxiv.org/abs/2503.20162
Salas, J. (2025). Certificate-Sensitive Subset Sum: Realizing Instance Complexity. arXiv preprint arXiv:2507.15511.
Hirahara, S. (2023). Capturing one-way functions via NP-hardness of meta-complexity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023) (pp. 1027–1038). Association for Computing Machinery. https://doi.org/10.1145/3564246.3585130
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Articles are open access under the Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Authors who publish a manuscript in this journal agree to the following terms:
- The authors reserve the right to authorship of their work and transfer to the journal the right of first publication under the terms of the Creative Commons Attribution License, which allows others to freely distribute the published work with a mandatory link to the the original work and the first publication of the work in this journal.
- Authors have the right to conclude independent additional agreements that relate to the non-exclusive distribution of the work in the form in which it was published by this journal (for example, to post the work in the electronic repository of the institution or publish as part of a monograph), providing the link to the first publication of the work in this journal.
- Other terms stated in the Copyright Agreement.