Methods for efficient generation of Turing machines to solve NP-hard problems
https://doi.org/10.21285/2227-2917-2024-3-556-569
EDN: QJQXZL
Abstract
The present study analyzes the software implementation of the concept of generating Turing machines that solve NP-hard problems. The paper describes a mathematical formulation of machine generation, presented as a solution of resource planning problems to be adapted to software for designing class schedules or, more generally, for network scheduling. The proposed software solutions for data representation are partially based on technical solutions for designing a class schedule. Basic strategies (procedural semantics of methods) for reducing searces (deep return, look ahead, etc.) utilize technical solutions for designing class schedules and other strategies (e.g., application of oracle) that have not been used for this purpose. The study is aimed at analyzing the intermediate results of software implementation of the concept of generating Turing machines that solve NP-hard problems. The paper proposes further plans for developing a software package for generating Turing machines into an open platform for teaching students the theory of algorithms and information technology, conducting experiments to determine the non-polynomial complexity of solving certain NP-hard problems generated by Turing machines.
About the Authors
V. I. Martyanov
Irkutsk National Research Technical University ; Baikal State University ; Irkutsk State University
Russian Federation
Russian Federation
Vladimir I. Martyanov, Dr. Sci. (Phys.-Math.), Professor of the Department of Highways
Author ID: 2477
83 Lermontov St., Irkutsk 664074
11 Lenin St., Irkutsk 664003
1 Karl Marx St., Irkutsk 664003
A. S. Volkov
Baikal State University
Russian Federation
Russian Federation
Andrey S. Volkov, Postgraduate Student
11 Lenin St., Irkutsk 66403
References
1. Mart'yanov V.I. Draft Program Complex for Generating Turing Machines Solving Np-Hard Problems. Proceedings of Universities. Investment. Construction. Real estate. 2023;13(2):285-297. (In Russ.). https://doi.org/10.21285/2227-2917-2023-2-285-297. EDN: UAEWDT.
2. Mart'yanov V.I. Logical-Heuristic Methods of Network Planning and Situation Recognition. In: Problemy upravleniya i modelirovaniya v slozhnykh sistemakh = Problems of Control and Modeling in Complex Systems. Samara; 2001. p. 203–215. (In Russ.).
3. Mart'yanov V.I., Arkhipov V.V., Katashevtsev M.D., Pakhomov D.V. Logic-Heuristic Methods for Solving Combinatorial Problems of High Complexity Applications Preview. Modern technologies. System analysis. Modeling. 2010;4(28):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 = Application Systems. Moscow: Institute of Design Automation of the Russian Academy of Sciences; 1992. p. 46–58. (In Russ).
5. Lagutenkov A.V. Cryptocurrencies. Application Rules. Nauka i zhizn'. 2018;2:22-26. (In Russ.).
6. Kharpal A. All You Need to Know About the Top 5 Cryptocurrencies. Yahoo! Finance. 2017. Available from: https://finance.yahoo.com/news/know-top-5-cryptocurrencies-093231173.html [Accessed 20th May 2024].
7. Wilson-Nunn D., Zenil H. On the Complexity and Behaviour of Cryptocurrencies Compared to Other Markets. Cornell University: arxiv. 2014:1-16. https://doi.org/10.48550/arXiv.1411.1924.
8. Eremeev A.V., Zaozerskaya L.A., Kolokolov A.A. The Set Covering Problem: Complexity, Algorithms, and Experimental Investigations. Discrete Analysis and Operations Research. 2000;7(2):22-46. (In Russ). EDN: IBBFDL.
9. Mart'yanov V.I., Vyatkin I.V., Mogil'nitskii E.Yu. Theoretical and Implementation Aspects of Some Classes of Network Management Tasks. In: Problemy upravleniya i modelirovaniya v slozhnykh sistemakh = Problems of Control and Modeling in Complex Systems. Samara; 1999. p. 203–208. (In Russ.).
10. Mart'yanov V.I. NP-Difficult Tasks: Automatic Proof of Theorems and Turing’s Machine. Baikal Research Journal. 2021;12(4):1-9. (In Russ.). https://doi.org/10.17150/2411-6262.2021.12(4).11. EDN: HJXXGO.
11. Knut D.E. The Art of Computer Programming: Basic Algorithms. Moscow: Mir, 1976. 736 p. (In Russ.).
12. Knut D.E. The Art of Computer Programming: Sorting and Searching. Moscow: Mir, 1978. 848 p. (In Russ.).
13. Mart'yanov V.I., Kulik N.S., Pakhomov D.V., Bol'shakov E.A. Project of The System to Control Irkutsk Regional Automobile Road Network. Proceedings of Irkutsk State Technical University. 2014;4(87):118-123. (In Russ.). EDN: SBNFNJ.
14. Kulik N.S., Mart'yanov V.I., Pakhomov D.V. Building A Motorway Graph for The Heavy Trucks Tolling System. Proceedings of Irkutsk State Technical University. 2016;4(111):96-101. (In Russ.). EDN: VVSOFF
15. Mart'yanov V.I., Pakhomov D.V., Arkhipov V.V. Network Planning of the Maintenance of the Highway Network of the Irkutsk Region. In: Novye tekhnologii v investitsionno-stroitel'noi sfere i ZhKKh: sbornik nauchnykh trudov = New Technologies in The Investment and Construction Sector and Housing and Communal Services: A Collection of Scientific Papers. 14 April 2005, Irkutsk. Irkutsk; 2005. vol. 1, р. 123–129. (In Russ.).
16. Mart'yanov V.I. Set-Theoretical Data Models in The Problem of Calculating Secondary Structures of RNA. System Analysis and Mathematical Modeling. 2022;4(4):343-357. (In Russ.). https://doi.org/10.17150/2713-1734.2022.4(4).343-357. EDN: VUNLFX.
17. Mart'yanov V.I., Korol'kov Yu.D. Set-Theoretic Models of Complex Systems and Intellectual Support Algorithms. Irkutsk: Publishing House of Baikal State University. 2020. 125 p. (In Russ.).
18. Mart'yanov V.I., Katashevtsev M.D. Computer Processing of Distorted Video Sequences Obtained by Mobile Road Laboratories. IOP Conference Series: Materials Science and Engineering. 2019;667(1):1-9. http://doi.org/10.1088/1757-899X/667/1/012060.
19. Mart'yanov V.I. Set-Theory Analysis of the Data Organization of the Educational Process and Algorithms for Designing a Schedule with Elements Artificial Intelligence. Bulletin of Baikal State University. 2020;30(4):575-585. (In Russ.). https://doi.org/10.17150/2500-2759.2020.30(4).575-585. EDN: QKOCYX.
20. Shcherbina O.A. Constraint Satisfaction and Constraint Programming. Intelligent Systems.Theory and Applications. 2011;15(1-4):53-170. (In Russ.). EDN: PWUSTF.
21. Hentenryck van P. Constraint Satisfaction in Logic Programming. Cambridge: The MIT Press, 1989. 224 p.
22. Styuart I. The Greatest Math Problems. Moscow: Alpina non-fiction, 2015. 584 p. (In Russ.).
23. Razborov A.A. Algebraic Complexity. Moscow: Moscow Center for Continuing Mathematical Education, 2016. 32 p.
24. Fortnow L. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton: Princeton University Press. 2017. 176 p.
25. Leeuwen van J. Handbook of Theoretical Computer Science. Cambridge: The MIT Press, 1990. 1014 p.
26. Knuth D.E. Postscript about NP-hard problems. ACM SIGACT News. 1974;6(2):15-16. https://doi.org/10.1145/1008304.1008305.
27. Aaronson S. The Scientific Case for P≠NP. Shtetl-Optimized. 2014. Available from: https://scot-taaronson.blog/?p=1720 [Accessed 20th May 2024].
28. Aaronson S. Quantum Computing Since Democritus Lecture 6: P, NP, and Friends. Shtetl-Optimized. 2006. Available from: https://scottaaronson.blog/?p=149 [Accessed 20th May 2024].
29. Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. New York: John Wiley & Sons, 1985. 476 p.
30. Wegener I. Complexity Theory: Exploring the Limits of Efficient Algorithms. New York: Springer, 2005. 320 p.
Review
For citations:
Martyanov V.I., Volkov A.S. Methods for efficient generation of Turing machines to solve NP-hard problems. Izvestiya vuzov. Investitsii. Stroitelstvo. Nedvizhimost. 2024;14(3):556-569. (In Russ.) https://doi.org/10.21285/2227-2917-2024-3-556-569. EDN: QJQXZL
Views:
68
Email this article 