A REFINED CLASSIFICATION OF THE SUBSET SUM PROBLEM IN POLYNOMIAL TIME COMPLEXITY

• Published in: Turkish journal of computer and mathematics education 2024-09, Vol.15 (3), p.301-311
• Main Authors: Sinchev, B, Sinchev, A B, Mukhanova, A M
• Format: Article
• Language: English
• Subjects: Algorithms; Arrays; Complexity; Diophantine equation; Integers; Polynomials; Problem solving
• ISSN: 1309-4653
• DOI: 10.61841/turcomat.v15i3.14804

The problem considered is the selection of at least one subset from a set (array) of distinct positive integers, such that the sum of the subset's elements exactly matches a given target sum (target certificate). According to R. M. Karp, this problem belongs to the class of NP-complete problems. Diophantine equations and an auxiliary problem, which facilitates the solution of the original problem and has independent scientific interest, have been introduced. A novel method has been developed, which includes proven lemmas and theorems. These results enable the development of efficient and straightforward algorithms for solving the subset sum problem. The time and space complexity for selecting the required subsets do not exceed the square of the length of the original set. An analytical framework has been proposed for managing indices within the original set. These algorithms are applicable to solving problems related to the independent set of cardinality к and the ^-vertex cover problem. Additionally, we present examples to confirm claimed results. It should be noted that the time complexity of sorting an array of integers is proportional to the square of the array's size, and this problem belongs to class P. Therefore, based on the newly developed method, it can be inferred that the subset sum problem, originally classified as NP-complete within the NP class, also belongs to P.