Project objective

To develop efficient methods and algorithms for solving NP-complete problems based on the solution of the subset sum problem. The proposed methods will rely on a power management system and targeted certification of input sets and output subsets using set theory and its operations. This approach aims to create new algorithms applicable to a wide range of combinatorial problems, such as knapsack and scheduling tasks, with the potential for commercialization and large-scale application.

Relevance

To date, there have been several results worldwide concerning the design of algorithms for NP-complete problems, including exponential and pseudo-polynomial algorithms. However, the time complexity of these algorithms significantly exceeds that which is anticipated in our project. In contrast, the proposed algorithms will have a time complexity proportional to the square of the length of the input data (input set), representing a significant advancement in algorithmic theory. Thus, the project not only deepens existing knowledge but also addresses pressing scientific questions that remain unresolved in previous research.

The implementation of the project will have a positive impact on the level of research and the scientific and technical potential in the field of algorithmic research. The proposed solutions are expected to increase the competitiveness of the scientific organizations that will implement and apply them. The social and economic effect of introducing the developed algorithms will manifest itself in the increased efficiency of computing systems, which in turn will improve the quality of services and products across various industries. Achieving the expected effect will require funding for further research, support for the commercialization of results, and active cooperation with industry to introduce the algorithms into real business processes.

Project significance

The results of the project hold significant importance at both national and international levels. In the context of rapidly advancing technologies and the growing need for efficient computational solutions, the proposed algorithms have the potential to substantially reduce the execution time of tasks on modern computing platforms. This, in turn, may lead to increased social and economic interest, as algorithm optimization directly impacts performance in areas such as logistics, planning, and resource management. The project results are expected to be in demand in both the private and public sectors.

Expected results

In 2025–2027, analytical, interim and final R&D reports will be prepared. The results of the project will be fast (in time and space) algorithms and software, proportional to the square of the length of the input data and independent of its binary representation.

Dissemination of information about the project is planned through participation in exhibitions, seminars, online conferences, publications in specialized media and meetings with leading manufacturers. The research will be competitive on the world market, as it is focused on the use of machine learning and artificial intelligence methods and can be applied commercially to combinatorial problems such as loading aircraft and sea vessels, scheduling airports, classes and others. The results will contribute to raising the level of digital competence in Kazakhstan.

Achieved results

The project is based on previously obtained results published in our articles and US patents, which pertain to the subset sum problem with small output set cardinality. These results were presented at the Ninth International Congress on Information and Communication Technology in London, with publication in the Springer Link series.

These studies demonstrated the potential for developing new approaches to solving NP-complete problems, serving as a foundation for further in-depth study and the creation of more efficient algorithms.

Publications (2022–2024)

1. Sinchev B., Sinchev A.B., Mukhanova A.M. Algorithm Based on the Subset Sum Problem for High Performance Computing // Lecture Notes in Networks and Systems. 2024. Vol. 1002. P. 627–637. DOI: 10.1007/978-981-97-3299-9_51
2. Sinchev B., Mukhanova A., Auezova A., Sadykova T. Polynomial Solvability of the Subset Sum Problem // SIST 2022 — International Conference on Smart Information Systems and Technologies, Proceedings. 2022. DOI: 10.1109/SIST54437.2022.9945761

Patents

1. Sinchev B., Sinchev A.B., Akzhanova Z.A., Issekeshev Y. Computing network architecture for reducing a computing operation time and memory usage associated with determining, from a set of data elements, a subset of at least two data elements, associated with a target computing operation result. US Patent 10,860,317 B2, 2020.
2. Sinchev B., Sinchev A., Akzhanova Z. Computing Network Architecture for Reducing a Computing Operation Time and Memory Usage Associated with Determining, from a Set of Data Elements, a Subset of at Least Two Data Elements, Associated with a Target Computing Operation Result. US Patent 10,394,555 B1, 2019.

Research team