inner-banner-bg

Current Research in Statistics & Mathematics(CRSM)

ISSN: 2994-9459 | DOI: 10.33140/CRSM

Track Your Submission
image
image
image
Current Research in Statistics & Mathematics
Share this page:    
Indexing
img
Submit Manuscript
Open Access Journals
View More
Viewers & Readers
web page visitor counter

Research Article - (2025) Volume 4, Issue 2

View PDF Download PDF

Partitions, the P Versus NP Problem and Applications

Vassilly Voinov *
 
Independent scholar, Almaty, Kazakhstan
 
*Corresponding Author: Vassilly Voinov, Independent scholar, Almaty, Kazakhstan

Received Date: Apr 07, 2025 / Accepted Date: May 07, 2025 / Published Date: May 21, 2025

Copyright: ©2025 Vassilly Voinov. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Citation: Voinov, V. (2025). Partitions, the P Versus NP Problem and Applications. Curr Res Stat Math, 4(2), 01-13.

Abstract

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 O(nlogn) 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.

Keywords

Integer Linear Programming, Combinatorics, Partitions, Polynomial Time Algorithms, Public-Key Cryptography, P =Np

Introduction


 

Conclusion

Declarations

  • Funding: Not applicable
  • Conflict of Interest: Not applicable
  • Ethics Approval and Consent to Participate: Not applicable
  • Consent for Publication: Not applicable
  • Data Availability: All data except Table 1 from Voinov [17] were obtained in this research
  • Materials Availability: Not applicable
  • Code Availability: R-scripts developed and used are given in appendices
  • Author Contribution: Not available

 

 

Acknowledgements

The author is grateful to Hazell Mitchell for her enormous help in this article publishing.

References

  1. Adel'son-Vel'skii, G. M. (1962). An algorithm for the organization of information. Soviet Math., 3, 1259-1263.
  2. Cook, S.: The P versus NP problem. (2000). https://www. claymath.org/pvsnp.
  3. Garey, M. R., & Johnson, D. S. (1978). ``strong''np- completeness results: Motivation, examples, and implications. Journal of the ACM (JACM), 25(3), 499-508.
  4. Garey, M., D. Johnson, D.: (1979). Computers and Intractability: A Guide to the theory of NP- Completeness. Freeman W.H. and Co., New York.
  5. Genitrini, A., & Pépin, M. (2021). Lexicographic unranking of combinations revisited. Algorithms, 14(3), 97.
  6. Karp, R. M. (2009). Reducibility among combinatorial problems. In 50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art (pp. 219-241). Berlin, Heidelberg: Springer Berlin Heidelberg.
  7. Kyritsis, C. K. (2021). Review of the Solutions of the Clay Millennium Problem about P≠ NP= EXPTIME. World Journal of Research and Review, 13(3), 21-26.
  8. LaPlante, M. (2015). A polynomial time algorithm for solving clique problems. arXiv preprint arXiv:1503.04794.
  9. Nijenhuis, A., & Wilf, H. S. (2014). Combinatorial algorithms: for computers and calculators. Elsevier.
  10. Panyukov, A. (2014). Polynomial solvability of $ NP $-complete problems. arXiv preprint arXiv:1409.0375.
  11. Pya Arnqvist, N., Voinov, V., Makarov, R., Voinov, Y.:”nilde”: Non-negative integer solutions of linear Diophantine equations with applications (2021). R-package version 1.1- 7. https://CRAN, R-project.org/package-nilde, https://doi. org/10.13140/RG.2.2.26198.19523
  1. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.
  2. Tan, S. K. (2021, July). Prove Np not equal P using Markov Random Field and Boolean Algebra Simplification.
  3. Voinov, V., & Nikulin, M. (1995). Generating functions, problems of additive number theory, and some statistical applications. Revue Roumaine de Mathematiques Pures et Appliquees, 40(2), 107-148.
  4. Voinov, V., Nikulin, M. (1995b). Corrigendum, Romanian journal of pure and applied mathematics 41(9-10), 713.
  5. Voinov, V. G., & Nikulin, M. S. (1997). On a subset sum algorithm and its probabilistic and other applications.
  6. Voinov, V. (2023). An experimental supported by some strong theoretical arguments proof of the fundamental equality P= NP. Central Asia Business Journal.
  7. Voinov, V. (2023b). A simple enumerative polynomial-time algorithm for the prime factorization. Central Asian Business Journal 23(2), 1-6.
  8. Voinov, V., Arnqvist, N. P., & Voinov, Y. (2018). Polynomial in time nonnegative integer solutions of knapsacks and similar problems in R: P= NP?. Mathematical Journal, 18(2), 47-58.
  9. Voinov, V., Makarov, R., & Voinov, Y. (2019). An exact polynomial in time solution of the one-dimensional bin- packing problem. Submitted to ASMDA, 2019.
  10. Voinov, V., & Pya Arnqvist, N. (2021). An exact polynomial- time algorithm for the optimal solution of traveling salesman problems. Central Asia Business Journal, 12(4), 17-32.
  11. Voinov, V. (2022). An algorithm for deriving classical and Generalized Frobenius numbers: applications in tiling and storing. Central Asian Business Journal 13(1), 23-35.
  12. Duan, W. Q. (2012). A constructive algorithm to prove P= NP. arXiv preprint arXiv:1208.0542.
  13. Woeginger, G. J. (2016). P-versus-NP page. url: https://www. win. tue. nl/~ gwoegi. P-versus-NP. htm.(Retrieved September 13, 2021).
  14. Yang, Z. (2011). A non-canonical example to support P is not equal to NP. Transactions of Tianjin University, 17, 446-449.
  15. Zeilberger, D. (2023). Research Announcement: A Computer- Generated Proof that P= NP.

Appendix