Draft program complex for generating Turing machines solving NP-hard problems
https://doi.org/10.21285/2227-2917-2023-1-285-297
Abstract
This paper provides an overview of the progress made in the software implementation of the concept for generating Turing machines that solve NP-hard problems. Plans are discussed for developing a software package for generating Turing machines, with the potential to serve as an open-source educational platform for learning algorithm theory and information technologies. The proposed program complex also encompasses the opportunity for interested individuals to conduct experiments aimed at determining the NP-hardness of specific problem series generated by Turing machines; participating in the generation of Turing machines and solving NP-hard problems on personal computers; transferring the calculation results to a platform, similar to the generator of cryptocurrencies, which focuses on searching for timeless mathematical objects, instead of creating artificially generated blocks of numbers for a short period. It is noted that the idea of using constraint satisfaction methods to generate Turing machines for solving tape NP-hard problems extends the boundaries of constraint programming. Furthermore, it holds the potential for contributing to the resolution of the long-standing question regarding the equality of polynomial and NP-hardness (P =? NP) – one of the seven unsolved problems of the third millennium in mathematics to this day.
About the Author
V. I. Martyanov
Irkutsk National Research Technical University; Baikal State University; Irkutsk State University
Russian Federation
Competing Interests:
Russian Federation
Vladimir I. Martyanov 0 Dr. Sci. (Phys.-Math.), Professor of the Department of Highways, Irkutsk NRTU; Baikal SU, Russia Irkutsk SU.
83 Lermontov St., Irkutsk 664074; 11 Lenin St., Irkutsk 664003; 1 Karl Marx St., Irkutsk 664003
Competing Interests:
The author declare no conflict of interests regarding the publication of this article
References
1. Mart'yanov V.I. NP-difficult tasks: automatic proof of theorems and Turing’s machine. Baikal Research Journal. 2021;12(4):11. (In Russ.). https://doi.org/10.17150/2411-6262.2021.12(4).11.
2. Mart'yanov V.I. Logical-heuristic methods of network planning and situation recognition. Problemy upravleniya i modelirovaniya v slozhnykh sistemakh. Samara; 2001. p. 203-215. (In Russ.).
3. Martyanov V.I., Arkhipov V.V., Katashevzev V.I. Martyanov, V.V. Arkhipov, M, Pakhomov D.V. Logicheuristic methods for solving combinatorial problems of high complexity applications preview. Sovremennye tekhnologii. Sistemnyi analiz. Modelirovanie = Modern technologies. System analysis. Modeling. 2010;4:205-211. (In Russ.). EDN: NRBKXP.
4. Martyanov V.I., Sukhorutchenko V.V., Okuntsov V.V. Planning of information flows in a hierarchical system. In: Prikladnye sistemy. Moscow: Institute of Design Automation of the Russian Academy of Sciences; 1992. p. 46–58. (In Russ.).
5. Martyanov V.I., Vyatkin I.V., Mogil'nitskii E.Yu. Theoretical and implementation aspects of some classes of network management tasks. Problemy upravleniya i modelirovaniya v slozhnykh sistemakh. Samara; 1999. p. 203-208. (In Russ.).
6. Lagutenkov A.V. Cryptocurrencies. Application rules. Nauka i zhizn'. 2018;2:22-26. (In Russ.).
7. Kharpal A. All you need to know about the top 5 cryptocurrencies. Yahoo! Available from: https://finance.yahoo.com/news/know-top-5cryptocurrencies-093231173.html [Accessed 14th March 2023].
8. Wilson-Nunn D., Zenil H. On the Complexity and Behaviour of Cryptocurrencies Compared to Other Markets. Research Gate. Available from: https://www.researchgate.net/publication/268079329_On_the_Complexity_and_Behaviour_of_Cryptocurrencies_Compared_to_Other_Markets [Accessed 14th March 2023].
9. Shcherbina O.A. Udovletvorenie ogranichenii i programmirovanie v ogranicheniyakh (preprint). Vienna: University of Vienna; 2012. 118 p. (In Russ.).
10. Hentenryck van P. Constraint Satisfaction in Logic Programming. Cambridge: The MIT Press; 1989. 356 p.
11. Stewart I. The great mathematical problems. Moscow: Al'pina non-fikshn; 2015. 460 p. (In Russ.).
12. Razborov A.A. Algebraic complexity. Moscow: Moscow Center for Continuing Mathematical Education; 2016. 32 p. (In Russ.).
13. Fortnow L. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton: Princeton University Press; 2013.
14. Mal'tsev A.I. Algorithms and recursive functions. Moscow: Nauka; 1965. 392 p.
15. Korolkov Yu.D., Martianov V.I. Discrete models: representation by finite trees and solvability of formal theories. Irkutsk: Irkutsk National Research Technical University; 2017. 160 p. (In Russ.).
16. Martyanov V.I., Kulik N.I., Pakhomov D.V., Bolshakov E.A. Project of the system to control Irkutsk regional automobile road network. Vestnik Irkutskogo gosudarstvennogo tekhnicheskogo universiteta = Proceedings of Irkutsk State Technical University. 2014;4:118-123. EDN: SBNFNJ.
17. Kulik N.S., Martyanov V.I., Pakhomov D.V. Building a motorway graph for the heavy trucks tolling system. Vestnik Irkutskogo gosudarstvennogo tekhnicheskogo universiteta = Proceedings of Irkutsk State Technical University. 2016. № 4 (111). С. 96–101. (In Russ.). EDN: VVSOFF. https://doi.org/10.21285/1814-3520-2016-4-96-101.
18. Martyanov V.I., Pakhomov D.V., Arkhipov V.V. Network planning of the maintenance of the highway network of the Irkutsk region. Novye tekhnologii v investitsionno-stroitel'noi sfere i ZhKKh: sb. nauch. trudov: in 2 vol. Vol. 1. Irkutsk: Irkutsk State Technical University; 2005. p. 123-129. (In Russ.).
19. Martyanov V.I. Set-theoretical data models in the problem of calculating secondary structures of RNA. System Analysis & Mathematical Modeling. 2022;4(4):343-357. EDN: VUNLFX. https://doi.org/10.17150/2713-1734.2022.4(4).343-357.
20. Martianov V.I., Korolkov Yu.D. Set-theoretic models of complex systems and algorithms of intellectual support. Irkutsk: Baikal State University; 2020. 188 p. (In Russ.).
21. Martianov V.I., Katashevtsev M.D. Computer processing of distorted video sequences obtained by mobile road laboratories. Investments, Construction, Real Estate: New Technologies and Special-Purpose Development Priorities: IOP Conference Series: Materials Science and Engineering (Irkutsk, 25 April 2019). 2019. Vol. 667. https://doi.org/10.1088/1757-899X/667/1/012060.
22. Martyanov V.I. Set-theory analysis of the data organization and algorithms for net planning with elements artificial intelligence. Prikladnye problemy diskretnogo analiza: sbornik nauchnyh trudov. 2021;90-100. (In Russ.). EDN: BVANFU.
23. Leeuwen J.V. Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier, 1998. 1020 p.
24. Knuth D. Postscript about NP-hard problems. ACM SIGACT News. 1974;6(2):15-16. https://doi.org/10.1145/1008304.1008305.
25. Aaronson S. The Scientific Case for P≠NP. Shtetl-Optimized. Available from: https://scottaaronson.blog/?p=1720 (25.09.2016). [Accessed 14th March 2023].
26. Aaronson S. PHYS771 Lecture 6: P, NP, and Friends. Scott Aaronson.ru. Available from: https://www.scottaaronson.com/democritus/lec6.html [Accessed 14th March 2023].
27. Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. The Traveling Salesman Problem: A Guid-ed Tour of Combinatorial Optimization, John Wiley & Sons, 1985.
28. Wegener I. Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer, 2005. P. 189. https://doi.org/10.1007/3-540-27477-4.
Review
For citations:
Martyanov V.I. Draft program complex for generating Turing machines solving NP-hard problems. Izvestiya vuzov. Investitsii. Stroitelstvo. Nedvizhimost. 2023;13(2):285-297. (In Russ.) https://doi.org/10.21285/2227-2917-2023-1-285-297
Views:
120
Email this article 