A refined version of the algorithm for constructing all 0-1 integer solutions for linear Diophantine equations is introduced. The correctness and its polynomial time complexity is confirmed by a Monte Carlo experiment that uses the trivial simple combinatorics. An implementation of this algorithm proves the polynomial time solvability of many business decision and optimization problems that are currently considered as being intractable: bin packing and cutting stock, open-shop and job-shop scheduling, production planning, dynamic storage allocation and many others. It is shown that all these problems admit polynomial time algorithms for their solution. An experimental proof of the important for the theory fact that every planar symmetric graph possesses at least one Hamiltonian circuit is given.
A much faster exact polynomial time algorithm for solving symmetric traveling salesman problems is suggested. The algorithm shows that such problems may have several optimal solutions. Numeric randomly generated instances with such solutions that can be used as test examples for newly developed algorithms are presented.
Results of this research present a reliable experimental proof of the fundamental equality P=NP.
AMS subject classifications (2010): 05A18, 05C45, 90C10, 90C27, 11D04, 68Q15, 68Q17
- Cook, S. (2005). The P versus NP problem. https://www.claymath.org, accessed on Jan. 10, 2023.
- Diaby, M. (2007). The Traveling Salesman Problem: A Linear Programming Formulation. WSEAS Transactions on Math, 6(6), 745-754. arxiv.org/ftp/cs/papers/0609/0609005.pdf.
- Garey, M. & Johnson, D. (1978). “Strong” NP-Completeness Results: Motivation, Examples, and Implications. Journal of ACM, 25(3), 499-508.
- Garey, M. & Johnson, D. (1979). Computers and Intractability: A Guide to the theory of NP- Completeness, W.H.Freeman & Co., NY.
- Kyritis, K. (2021). Review of the solutions of the Clay Millennium problem about P≠NP=EXPTIME. World J. of Research and Review, 13(3), 21-26. https://doi.org/10.31871/WJRR.13.3.8.
- Laporte, G. (1992). The Traveling Salesman Problem: An overview of exact and approximate algorithms. European J. of Operational Research, 59, 231-247. https://doi.org/10.1016/0377-2217(92)90138-Y.
- Müeller, M. (2020). Polynomial Exact-3-SAT-Solving Algorithm, International Journal of Engineering Technologies, 9(3), 1-55. https://doi:10.14419/ijet.v9i3.30749.
- Nijenhuis, A. & Wilf, H. (1978). Combinatorial Algorithms for Computers and Calculators. NY; Academic Press.
- Voinov, V. & Nikulin, M. (1995). Generating functions, problems of additive number theory, and some statistical applications. Romanian J. of Pure and Applied Mathematics, 40, 107-147.
- Voinov, V. & Nikulin, M. (1997). On a subset sum algorithm and its probabilistic and other applications. Balakrishnan, N, ed.- Advances in Combinatorial Methods and Applications to Probability and Statistics. Boston: Birkhäuser, 153-163.
- Voinov, V. (2017). A note on the intractability of partitions, knapsack, subset sum and related problems. Mathematical Journal (ISSN 1682-0525), 17(4), 13-24.
- Voinov, V., Pya Arnqvist, N. & Voinov, Y. (2018). Polynomial in time nonnegative integer solutions of knapsack and similar problems in R: P=NP? Mathematical Journal, 18(2), 47- 58.
- Voinov, V. (2019). A note on serious arguments in favor of equality P=NP. 18th ASMDA Conf. Proceedings, 11-14 June 2019, Florence, Italy, 799-809.
- Voinov, V. & Rahmanov, M. (2020). 2-, 3-, and 4-Partition Problems and their Relation to the Equality P=NP. Central Asia Business Journal, 11(2), 34-46.
- 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.
- Voinov, V. (2022). An algorithm for deriving classical and Generalized Frobenius numbers: applications in tiling and storing. Central Asia Business Journal, 13(1), 23-35.
- Wen-Qi, D. (2012). A constructive algorithm to prove P=NP. http://arxiv.org/abs/1208.0542, accessed on Jan. 10, 2023.
- Woeginger, G. (2016). The P versus NP page. https://www.win.tue.nl/~gwoegi/P-versus-NP.htm, accessed on Jan. 10, 2023.
- Zeilberger, D. (2009.) Research Announcement: A Computer-Generated Proof that P=NP. http://www.math.rutgers.edu/~zeilberg/mamarimPDF/pnp.pdf, accessed on Jan. 10, 2023.
