ALGORITHMS OF NP-COMPLETE PROBLEMS. PART II
Б.К. Синчев, Aksulu Mukhanova, Tolkynai Sadykova · Scientific Journal of Astana IT University · 2025
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.