Name
Abstract | ||
|---|---|---|
In this paper we investigate the number partitioning problem, using the tropical semiring (max-plus algebra). We show that the problem is reduced to deciding whether one of integers is a solution of a tropical analogue of algebraic equations with coefficients composed of other integers. For n up to 6 we derive concretely and explicitly the equation and its solution set. The derivation requires only routine algebraic computations, so can be applied for n larger than 6. Our approach based on max-plus algebra reveals the mathematical structure of the problem and provides a new view point for the P versus NP problem, since the problem is well-known to be NP-complete. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.dam.2020.04.020 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
NP-complete,Partition problem,Tropical semiring,Max-plus algebra | Journal | 285 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Susumu Kubo | 1 | 0 | 0.34 |
| Katsuhiro Nishinari | 2 | 189 | 47.27 |