ALGORITHMS OF NP-COMPLETE PROBLEMS. PART I
The paper considers a parameterized formulation of the subset sum problem for an -element set of positive integers, where the sum of the selected elements equals a given certificate . A method for constructing subsets of fixed cardinality based on index certificates and two-dimensional arrays is proposed, enabling efficient subset selection without exhaustive enumeration. The core idea is to shift from the value space to the index space and to exploit structured array diagonals, which reduces the practical computational complexity for fixed . Algorithms for constructing subsets of even cardinality are presented, and their applicability to information retrieval and big data processing tasks is demonstrated, including unstructured information search, where processing speed and efficient memory usage are critical. It is emphasized that the obtained results correspond to a restricted and parameterized formulation of the problem and do not contradict the known NP-completeness of the general subset sum problem.
Сведения
- Опубликовано
- 2026 · Т. 23, № 1, С. 82-93
- Язык
- Английский
- ISSN
- 1998-6688 · 2959-8109
- Издатель
- Kazakh-British Technical University
- Аффилиации
- International Information Technology University
Q-university
National Information Technologies JSC