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.

1. Bellman, R. Notes on the Theory of Dynamic Programming IV – Maximization over Discrete Sets. Naval Research Logistics Quarterly 3 (1–2), 67–70 (1956).

2. Pisinger, D. Linear Time Algorithms for Knapsack Problems with Bounded Weights. Journal of Algorithms 33 (1), 1–14 (1999).

3. Koiliaris, K., and Xu C. A Faster Pseudopolynomial Time Algorithm for Subset Sum. In Proceedings of SODA ’17, 2017. Preprint, arXiv:1610.04712v2.

4. Bringmann, K. A Near-linear Pseudopolynomial Time Algorithm for Subset Sum. In Proceedings of SODA ’17, 2017. Preprint, arXiv:1610.04712v2.

5. Horowitz, E., and Sanni S. Computing Partitions with Application to the Knapsack Problem. Journal of the ACM, 21, 277–292 (1974).

6. 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).

7. 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.

8. Egmonds, J. Paths, Trees and Flowers. Canadian Journal of Mathematics, 17, 449–467 (1965).

9. Nikolaev, A.V. Geometricheskiy podkhod k zadache o razreze. Yaroslavl: Yaroslavl State University, 2014. (in Russian).

10. Ivan Rijsbergen, C.J. Information Retrieval. Glasgow: Department of Computer Science, University of Glasgow, 1979.

11. Adamansky, A. Overview of Full-text Search Methods and Algorithms. Novosibirsk: Novosibirsk State University, 2018.

12. Chen, Min, Shiwen Mao, Yin Zhang, and Victor C.M. Leung. Big Data: Related Technologies, Challenges, and Future Prospects. Springer, 2014.

13. Lifshitz, Y. Tochnye algoritmy i otkrytye problemy. In Sovremennye zadachi teoreticheskoy informatiki. Accessed September 18, 2025. URL: http://download.yandex.ru/class/... (in Russian).

14. Kulikov, A. Algoritmy NP-trudnykh zadach. Lektsii. Saint Petersburg: Computer Science Club of St. Petersburg Department of Steklov Mathematical Institute, 2009. (in Russian).

15. 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).

16. Sinchev, B., Sinchev, A.B., and Akzhanova, Z.A. Computing Network Architecture for Reducing a Computing Operation Time and Memory Usage… USPTO Patent, 2019.

17. Akl, S.G. Adaptive and Optimal Algorithms for Enumerating Permutations and Combinations. The Computer Journa, l 30, 433–436 (1987).

18. Hoare, C.A.R. Quicksort. The Computer Journal, 5, 10–16 (1962).

19. Cormen, Th., Leiserson, Ch., Rivest, R., and Stein, C. Algoritmy: postroenie i analiz. Moscow: Williams, 2005. (in Russian).