ALGORITHMS OF NP-COMPLETE PROBLEMS. PART I
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
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.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Algorithms and Data Compression
Advanced Graph Theory Research
Publication details
- Journal / source
- Herald of Kazakh-British technical university
- Volume
- 23
- Issue
- 1
- Pages
- 82–93
- Publication date
- 29 March 2026
- Language
- EN