A REFINED CLASSIFICATION OF THE SUBSET SUM PROBLEM IN POLYNOMIAL TIME COMPLEXITY
Main Article Content
Abstract
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 k and the k-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.
Downloads
Metrics
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
You are free to:
- Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
- Adapt — remix, transform, and build upon the material for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
Under the following terms:
- Attribution — You must give appropriate credit , provide a link to the license, and indicate if changes were made . You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
Notices:
You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation .
No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.
References
S.A. Cook. The complexity of theorem-proving procedures // STOC, 1971, pp.151–158.
R.M. Karp. Reducibility among combinatorial problems // Complexity of Computer Computations, 1972, IBM Research Symposia Series, pp.85–103.
B. Sinchev, A.B. Sinchev, A.M. Mukhanova. Algorithm based on the subset sum problem for high performance computing // Springer Link Proceedings of Ninth International Congress on Information and Communication Technology, 20 Jul 2024, pp.627-637
E. Horowitz, S. Sanni. Computing Partitions with Application to the Knapsack Problem // Journal of the ACM(JACM), 1974, T21, pp.277-292
R. Schroeppel, A. Shamir. A T=O(2n/2), S=O(2n/4) Algorithm for Certain NP-Complete Problem // SIAM Journal on Computing, 1981, Vol.10, № 3, pp.456-464
Н. Вирт. Алгоритмы и структуры данных. Пер. с англ. – М.: Мир, 2006.
B. Sinchev, A. Sinchev, J. Akzhanova, Y. Issekeshev, A. Mukhanova. Polynomial time algorithms for solving NP-complete problems // News of the National Academy of Sciences of Kazakhstan, Series of Geology and Technical Sciences, Volume 3, Number 441, 2020, pp.97-101
Б. Синчев. О полиномиальной разрешимости класса NP-complete // International journal of information and communication technologies, Том 2, Вып. 8, 2021, pp.67-71
B. Sinchev, A. B. Sinchev, Z.A. Akzhanova, Y. Issekeshev. 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 USPTO 10,860,317 B2, 2020, 34p.
Konstantinos Koiliaris, Chao Xu. A Faster pseudopolynomial time algorithm for subset sum // arXiv:1610.04712v2[cs.Ds], 8 Jan 2017, 18p.
K. Bringmann. A near-linear pseudopolynomial time algorithm for subset sum // arXiv:1610.04712v2[cs.Ds], 8 Jan 2017, 18p.
A. Lincoln, V. Williams, JR Wang, R. Williams. Deterministic Time-Space Tradeoffs for k-SUM // arXiv preprint arXiv:1605.07285