Algorithm Based on the Subset Sum Problem for High Performance Computing

被引：0

作者：

Sinchev, B. ^{[1
]}

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

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

机构：

[1] Int Univ Informat Technol, 34-1 Manas St, Alma Ata 050000, Kazakhstan

[2] Natl Informat Technol JSC, 55-15 Mangilik El Ave,Block C 2-3, Astana 010000, Kazakhstan

[3] Almaty Univ Technol, Tole Bi St 100, Alma Ata 050012, Kazakhstan

来源：

PROCEEDINGS OF NINTH INTERNATIONAL CONGRESS ON INFORMATION AND COMMUNICATION TECHNOLOGY, ICICT 2024, VOL 6 | 2024年 / 1002卷

关键词：

NP-complete class; Index management system; High performance computing;

D O I：

10.1007/978-981-97-3299-9_51

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We present a polynomial solution of the subset sum problem with time complexity T <= O(kn) <= O(n(2)) and space complexity S <= O((n-1)n/2 <= O (n(2)). The solution is based on a newly proposed initial set indexes' management system and provides a variety of applications including: scheduling, queries in databases, graph problems, and others. The suggested algorithm can be computed as a standalone, self-contained module or implemented as hardware chips. The scientific novelty of the approach represents a significant advancement in addressing the "P vs NP" millennium prize problem.

引用

页码：627 / 637

页数：11

共 18 条

[1]

[Anonymous], 1964, P C LOG METH PHIL SC

[2]

BELLMAN R., 1956, Naval Res. Logist. Quart., V3, P67, DOI [10.1002/nav.3800030107, DOI 10.1002/NAV.3800030107]

[3]

Bringmann K, 2017, PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1073

[4] PATHS TREES AND FLOWERS [J].

EDMONDS, J .

CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (03) :449-&

[5]

Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness

[6]

GuruswamiV MakarychevY, 2011, INNOVATIONS COMPUTER, P321

[7]

Hennessy J. L., 2011, Computer architecture: a quantitative approach

[8] COMPUTING PARTITIONS WITH APPLICATIONS TO KNAPSACK PROBLEM [J].

HOROWITZ, E ;

SAHNI, S .

JOURNAL OF THE ACM, 1974, 21 (02) :277-292

[9]

Karp Richard M, 1972, Complexity of Computer Computations, P85

[10]

Koiliaris K, 2017, arXiv

← 1 2 →