ALGORITHMS OF NP-COMPLETE PROBLEMS. PART II
DOI:
https://doi.org/10.37943/24MIOD6580Keywords:
NP-complete problems, polynomial algorithms, subset sum problem, big data, information retrievalAbstract
This paper presents an analytical and algorithmic framework for solving NP complete problems, specifically focusing on the Subset Sum Problem (SSP). The study aims to develop polynomial time algorithms capable of efficiency identifying a k-element subset from an n-element set of positive integers, where the sum of the elements equals a predefined certificate. In an n-element set of positive integers without repetition, the goal is to find a k-element subset ( ), whose sum of elements is equal to the certificate . In this second part of the work, a sample of a subset with odd power is considered (in the first part - a sample of with even power which determines the complexity of the proposed algorithms for solving the subset sum problem. The obtained USPTO patents [20] present a computer system for ultra-fast processing of big data with a volume of finite and a processing speed proportional to the execution time T with the required memory for power k=3. The proposed approach is based on the mapping , the arguments of which are the certificate and the elements of the set and the union of the required subsets obtained from the two-dimensional array from the set taking into account the mapping and the given certificate Then the sampling time of the subset of odd cardinality with the given certificate and the required space satisfy the conditions T , which are obtained based on solving the problem of the sum of the required subset from the set of natural numbers . Overall, the findings establish a theoretical foundation for ultra-fast computing systems and data-intensive applications, aligning with modern computational complexity and big data paradigms.
References
Bellman, R. (1956). Notes on the theory of dynamic programming IV – Maximization over discrete sets. Naval Research Logistics Quarterly, 3(1–2), 67–70. https://onlinelibrary.wiley.com/doi/10.1002/nav.3800030107
Pisinger, D. (1999). Linear time algorithms for knapsack problems with bounded weights. Journal of Algorithms, 33(1), 1 14. https://doi.org/10.1006/jagm.1999.1034
Quillillas, J., & Xu, C. (2021). Divide-and-conquer pseudo-polynomial algorithm for the subset sum problem. arXiv. https://arxiv.org/abs/2106.01234
Birgman, B. (2017). Pseudo-polynomial randomized algorithms for the subset sum problem. Journal of Discrete Algorithms, 45, 101–114. https://doi.org/10.1016/j.jda.2017.03.005
Horowitz, E., & Sahni, S. (1974). Computing partitions with applications to the knapsack problem. Journal of the ACM, 21(2), 277 292. https://doi.org/10.1145/321812.321824
Schroeppel, R., & Shamir, A. (1981). A more efficient algorithm for certain NP-complete problems. SIAM Journal on Computing, 10(3), 456 467. https://doi.org/10.1137/0210033
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
Martello, S., & Toth, P. (1990). Knapsack problems: Algorithms and computer implementations. John Wiley & Sons.
Manning, C., Raghavan, P., & Schütze, H. (2008). Introduction to information retrieval. Cambridge University Press.
Dean, J., & Ghemawat, S. (2008). MapReduce: Simplified data processing on large clusters. Communications of the ACM, 51(1), 107–113. https://doi.org/10.1145/1327452.1327492
Nguyen, D. T., & Hoang, T. Q. (2022). Advanced algorithmic techniques for NP-complete problems in big data analytics. Journal of Computational Science, 63, 101754. https://doi.org/10.1016/j.jocs.2022.101754
Wang, J., & Liu, T. (2022). Hybrid architectures for subset-sum optimization in large data systems. Information Sciences, 600, 345 362. https://doi.org/10.1016/j.ins.2022.04.015
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
Bonnetain, X., Bricout, R., Schrottenloher, A., & Shen, Y. (2020). Improved classical and quantum algorithms for Subset Sum. arXiv. https://arxiv.org/abs/2002.05276
Allcock, J., Hamoudi, Y., Joux, A., Klingelhöfer, F., & Santha, M. (2021). Classical and quantum algorithms for variants of Subset Sum via dynamic programming. arXiv. https://arxiv.org/abs/2111.07059
Wang, L., Xu, C., & Chen, Y. (2023). Recent advances in polynomial-time approximations for subset selection problems. Artificial Intelligence Review, 56(7), 6375 6401. https://doi.org/10.1007/s10462-023-10452-1
Zhang, Y., Chen, L., & Han, J. (2020). Efficient subset generation in large-scale data processing. IEEE Transactions on Knowledge and Data Engineering, 32(11), 2134 2146. https://arxiv.org/pdf/2411.06298
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.
Sinchev, B., Sinchev, A. B., & Akzhanova, Z. A. (2019). Computing network architecture for reducing computing operation time and memory usage associated with determining subsets from a data set. U.S. Patent No. 10,348,221. [20] Li, L. (2000). On the Arithmetic Operational Complexity for Solving Vandermonde Linear Equations. Japan Journal of Industrial and Applied Mathematics, 17(1). https://link.springer.com/article/10.1007/BF03167332
Luo, L., Li, C., & Li, Q. (2024). Deterministic Algorithms to Solve the (n,k)-Complete Hidden Subset Sum Problem. arXiv. https://arxiv.org/abs/2412.04967
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.