kaz29Вестник Казахстанско-Британского технического университетаHerald of the Kazakh-British Technical University1998-66882959-8109Казахстанско-Британский Технический Университет10.55452/1998-6688-2026-23-1-82-93kaz29-2502Research ArticleКОМПЬЮТЕРНЫЕ НАУКИCOMPUTER SCIENCEАЛГОРИТМЫ NP-ПОЛНЫХ ЗАДАЧ. ЧАСТЬ IALGORITHMS OF NP-COMPLETE PROBLEMS. PART Ihttps://orcid.org/0000-0001-9860-4491АуезоваА. С.AuyezovaA. S.

магистр, ассистент-профессор

г. Алматы

MSc., Assistant Professor

Almaty

a.auyezova@iitu.edu.kzhttps://orcid.org/0000-0001-6781-5501МухановаА. МMukhanovaA. M.

к.т.н., старший преподаватель

г. Алматы

Cand.Tech. Sc., Senior Lecturer

Almaty

nuraksulu72@mail.ruhttps://orcid.org/0000-0002-7333-2255СинчевА.SinchevA.

магистр

г. Астана

MSc.

Astana

askar.sinchev@gmail.comМеждународный университет информационных технологийКазахстанInternational Information Technology UniversityKazakhstanQ-universityКазахстанQ-universityKazakhstanNational Information Technologies JSCКазахстанNational Information Technologies JSCKazakhstan2026290320262318293Copyright © Ауезова А.С., Муханова А.М., Синчев А., 20262026Ауезова А.С., Муханова А.М., Синчев А.Auyezova A.S., Mukhanova A.M., Sinchev A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.kbtu.edu.kz/jour/article/view/2502

В работе рассматривается параметризованная постановка задачи о сумме подмножеств для n-элементного множества положительных целых чисел, сумма элементов которого равна заданному сертификату S. Предлагается метод формирования подмножеств фиксированной мощности k на основе индексных сертификатов и двумерных массивов, позволяющий эффективно выполнять выборку подмножеств без полного перебора. Основная идея заключается в переходе от значений элементов к индексному пространству и использовании структурированных диагоналей массивов, что снижает практическую трудоемкость вычислений при фиксированном k. Представлены алгоритмы формирования подмножеств четной мощности и показана их применимость в задачах поиска информации и обработки больших данных, а также на задачи поиска неструктурированной информации, где существенную роль играют скорость обработки и рациональное использование памяти. Подчеркивается, что полученные результаты относятся к ограниченной и параметризованной постановке задачи и не противоречат известной NP-полноте общей формулировки.

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.

NP-полные задачизадача о сумме подмножествполиномиальные алгоритмыдинамическое программированиебольшие данные (Big Data)поиск информацииNP-complete problemssubset sum problempolynomial algorithmsdynamic programmingBig Dataand information retrievalДанное исследование финансировалось Комитетом науки Министерства науки и высшего образования Республики Казахстан в рамках научного проекта «Разработка методов и быстрых алгоритмов разрешимости NP-complete задачи о сумме подмножеств» (ИРН AP26101119).ReferencesBellman R. Notes on the theory of dynamic programming IV – maximization over discrete sets // Naval Research Logistics Quarterly. – 1956. – Vol. 3, № 1–2. – P. 67–70.Bellman, R. Notes on the Theory of Dynamic Programming IV – Maximization over Discrete Sets. Naval Research Logistics Quarterly 3 (1–2), 67–70 (1956).Pisinger D. Linear time algorithms for knapsack problems with bounded weights // Journal of Algorithms. – 1999. – Vol. 33, № 1. – P. 1–14.Pisinger, D. Linear Time Algorithms for Knapsack Problems with Bounded Weights. Journal of Algorithms 33 (1), 1–14 (1999).Koiliaris K., Xu C. A faster pseudopolynomial time algorithm for subset sum // To appear in SODA ’17. – 2017. – 18 p. – URL: https://arxiv.org/abs/1610.04712v2.Koiliaris, K., and Xu C. A Faster Pseudopolynomial Time Algorithm for Subset Sum. In Proceedings of SODA ’17, 2017. Preprint, arXiv:1610.04712v2.Bringmann K. A near-linear pseudopolynomial time algorithm for subset sum // To appear in SODA’17. – 2017. – 18p. – URL: https://arxiv.org/abs/1610.04712v2.Bringmann, K. A Near-linear Pseudopolynomial Time Algorithm for Subset Sum. In Proceedings of SODA ’17, 2017. Preprint, arXiv:1610.04712v2.Horowitz E., Sanni S. Computing partitions with application to the knapsack problem // Journal of the ACM (JACM). – 1974. – Vol. 21. – P. 277–292.Horowitz, E., and Sanni S. Computing Partitions with Application to the Knapsack Problem. Journal of the ACM, 21, 277–292 (1974).Schroeppel R., Shamir A. A T=O(2^n/2), S=O(2^n/4) algorithm for certain NP-complete problem // SIAM Journal on Computing. – 1981. – Vol. 10, № 3. – P. 456–464.Schroeppel, R., and Shamir A. A T=O(2^n/2), S=O(2^n/4) Algorithm for Certain NP-Complete Problems. SIAM Journal on Computing, 10 (3), 456–464 (1981).Cobham A. The intrinsic computational difficulty of functions // Proceedings of the Congress for Logic, Methodology and Philosophy of Science. – North-Holland, 1964. – P. 24–30.Cobham, A. The Intrinsic Computational Difficulty of Functions. In Proceedings of the Congress for Logic, Methodology and Philosophy of Science, 24–30. Amsterdam: North-Holland, 1964.Egmonds J. Paths, trees and flowers // Canadian Journal of Mathematics. – 1965. – Vol. 17. – P. 449–467.Egmonds, J. Paths, Trees and Flowers. Canadian Journal of Mathematics, 17, 449–467 (1965).Николаев А.В. Геометрический подход к задаче о разрезе. – Ярославль: ЯрГУ, 2014. – 68 с.Nikolaev, A.V. Geometricheskiy podkhod k zadache o razreze. Yaroslavl: Yaroslavl State University, 2014. (in Russian).Ivan Rijsbergen C.J. Information Retrieval. – Glasgow: Dept. of Computer Science, University of Glasgow, 1979.Ivan Rijsbergen, C.J. Information Retrieval. Glasgow: Department of Computer Science, University of Glasgow, 1979.Adamansky A. Overview of full-text search methods and algorithms. – Novosibirsk: Novosibirsk State University, 2018. – 26 p.Adamansky, A. Overview of Full-text Search Methods and Algorithms. Novosibirsk: Novosibirsk State University, 2018.Chen M., Mao S., Zhang Y., Leung V.C.M. Big Data. Related Technologies, Challenges, and Future Prospects. – Springer, 2014. – 100 p.Chen, Min, Shiwen Mao, Yin Zhang, and Victor C.M. Leung. Big Data: Related Technologies, Challenges, and Future Prospects. Springer, 2014.Лифшиц Ю. Точные алгоритмы и открытые проблемы // Современные задачи теоретической информатики. – URL: http://download.yandex.ru/class/...Lifshitz, Y. Tochnye algoritmy i otkrytye problemy. In Sovremennye zadachi teoreticheskoy informatiki. Accessed September 18, 2025. URL: http://download.yandex.ru/class/... (in Russian).Куликов А. Алгоритмы NP-трудных задач. Лекции. – СПб: Computer Science клуб СПб отделения МИАН, 2009.Kulikov, A. Algoritmy NP-trudnykh zadach. Lektsii. Saint Petersburg: Computer Science Club of St. Petersburg Department of Steklov Mathematical Institute, 2009. (in Russian).Sinchev B., Sinchev A.B., Akzhanova J., Mukhanova A.M. New methods of information search. I // News of the National Academy of Sciences of Kazakhstan. Series of Geology and Technical Sciences. – 2019. – Vol. 3, № 435. – P. 240–246.Sinchev, B., Sinchev, A.B., Akzhanova, J., and Mukhanova, A.M. New Methods of Information Search. I. News of the National Academy of Sciences of Kazakhstan. Series of Geology and Technical Sciences, 3 (435), 240–246 (2019).Sinchev B., Sinchev A.B., Akzhanova Z.A. Computing network architecture for reducing computing operation time and memory usage… // Патент USPTO. – 2019. – 38 p.Sinchev, B., Sinchev, A.B., and Akzhanova, Z.A. Computing Network Architecture for Reducing a Computing Operation Time and Memory Usage… USPTO Patent, 2019.Akl S.G. Adaptive and optimal algorithms for enumerating permutations and combinations // The Computer Journal. – 1987. – Vol. 30. – P. 433–436.Akl, S.G. Adaptive and Optimal Algorithms for Enumerating Permutations and Combinations. The Computer Journa, l 30, 433–436 (1987).Hoare C.A.R. Quicksort // The Computer Journal. – 1962. – Vol. 5. – P. 10–16.Hoare, C.A.R. Quicksort. The Computer Journal, 5, 10–16 (1962).Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М.: Вильямс, 2005.Cormen, Th., Leiserson, Ch., Rivest, R., and Stein, C. Algoritmy: postroenie i analiz. Moscow: Williams, 2005. (in Russian).

The authors declare that there are no conflicts of interest present.