ALGORITHMS OF NP-COMPLETE PROBLEMS. PART I

Read full text Summarise with VIRAT
Authors: Anel Auyezova, Aksulu Mukhanova, A. B. Sinchev
Cited by: 0
References: 11

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