POLYNOMIAL TIME ALGORITHMS FOR SOLVING NP-COMPLETE PROBLEMS

被引：0

作者：

Sinchev, B. ^{[1
]}

Sinchev, A. B. ^{[2
]}

Akzhanova, Zh. ^{[3
]}

Issekeshev, Y. ^{[4
]}

Mukhanova, A. M. ^{[5
]}

机构：

[1] Int Univ Informat Technol, Alma Ata, Kazakhstan

[2] Natl Informat Technol JSC, Nur Sultan, Kazakhstan

[3] Fdn First President Elbasy, Nur Sultan, Kazakhstan

[4] ISS Corp, Alma Ata, Kazakhstan

[5] Almaty Univ Technol, Alma Ata, Kazakhstan

来源：

NEWS OF THE NATIONAL ACADEMY OF SCIENCES OF THE REPUBLIC OF KAZAKHSTAN-SERIES OF GEOLOGY AND TECHNICAL SCIENCES | 2020年 / 03期

关键词：

polynomial algorithms; the Subset Sum problem; NP-complete problems;

D O I：

10.32014/2020.2518-170X.59

中图分类号：

P [天文学、地球科学];

学科分类号：

07 ;

摘要：

The paper proposes algorithms with a polynomial time complexity and memory for solving the Subset Sum problem. The algorithm is obtained by using a combination function and mapping, the arguments of which are input data with a given length and a certificate. The work with indices of the input data is based on combination function and the combination generation algorithm. Mapping and combination function help to deal with an exponential time complexity of existing algorithms and solve combinatorial problems with constraints. In fact, the proposed algorithms solve the Millennium problem posed by S.A. Cook in a polynomial time. The proposed algorithms are applicable for input data with a given length together with the certificate with a given value.

引用

页码：97 / 101

页数：5

共 50 条

[31] Decidability of NP-Complete Problems
A. A. Vagis
A. M. Gupal
Cybernetics and Systems Analysis, 2022, 58 : 914 - 916
[32] Efficient DNA sticker algorithms for NP-complete graph problems
Zimmermann, KH
COMPUTER PHYSICS COMMUNICATIONS, 2002, 144 (03) : 297 - 309
[33] NP-complete problems for systems of Linear polynomial’s values divisibilities
Kosovskii N.K.
Kosovskaya T.M.
Kosovskii N.N.
Starchak M.R.
Vestnik St. Petersburg University, Mathematics, 2017, 50 (2) : 145 - 152
[34] Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines
Traversa, Fabio L.
Di Ventra, Massimiliano
CHAOS, 2017, 27 (02)
[35] Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
Abrams, DS
Lloyd, S
PHYSICAL REVIEW LETTERS, 1998, 81 (18) : 3992 - 3995
[36] Decidability of NP-Complete Problems
Vagis, A. A.
Gupal, A. M.
CYBERNETICS AND SYSTEMS ANALYSIS, 2022, 58 (06) : 914 - 916
[37] Solving NP-complete Problems using Quantum Weightless Neuron Nodes
de Paula Neto, Fernando M.
Ludermir, Teresa B.
de Oliveira, Wilson R.
da Silva, Adenilton J.
2015 BRAZILIAN CONFERENCE ON INTELLIGENT SYSTEMS (BRACIS 2015), 2015, : 258 - 263
[38] Solving numerical NP-complete problems with spiking neural P systems
Leporati, Alberto
Zandron, Claudio
Ferretti, Claudio
Mauri, Giancarlo
MEMBRANE COMPUTING, 2007, 4860 : 336 - 352
[39] Solving NP-complete problems using P systems with active membranes
Zandron, C
Ferretti, C
Mauri, G
UNCONVENTIONAL MODELS OF COMPUTATION UMC' 2K, PROCEEDINGS, 2001, : 289 - 301
[40] NEW EVOLUTIONARY GENETIC ALGORITHMS FOR NP-COMPLETE COMBINATORIAL OPTIMIZATION PROBLEMS
BAC, FQ
PEROV, VL
BIOLOGICAL CYBERNETICS, 1993, 69 (03) : 229 - 234

← 1 2 3 4 5 →