Partitions, the P Versus NP Problem and Applications

A new deterministic polynomial-time algorithm for sets of different positive integers partitioning has been introduced. The most important properties of the algorithm are that its time-complexity is 𝑂(𝑛𝑙𝑜𝑔𝑛) and that it is invariant w.r.t. the number of elements in a particular part. An implementation of this algorithm and the trivial combinatorial show that the classical Partition and the 4-Partition problem, currently considered to be in the NP-complete and the NP-complete in the strong sense complexity classes, respectively, are both solvable in polynomial time, thus belonging to class P. These results permit to introduce the P-complete class of problems reducible to each other by a polynomial transformation. Since it is a subclass of the NP-complete complexity class, from the well-established theory of NP-completeness, it immediately follows that P = NP. This intriguing research can be characterized as a constructive theoretical, supported by Monte Carlo simulations, proof of the fundamental equality P = NP. The presented results permit us to develop the most efficient deterministic algorithms for solving numerous practical problems in discrete mathematics, business, management, industry etc.