Central Asian Research Index

Scientific Journal of Astana IT University, 2025, с. 137-148

METHODS AND ALGORITHMS FOR SOLVING THE PROBLEM ON THE SUM OF SUBSETS

Anel Auyezova, Aigerim Aitim, Bakhtgerey Sinchev

Аннотация · Abstract

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.

Сведения · Details