inbureИзвестия вузов. Инвестиции. Строительство. НедвижимостьIzvestiya vuzov. Investitsii. Stroitelstvo. Nedvizhimost2227-29172500-154XIrkutsk National Research Technical University10.21285/2227-2917-2023-1-285-297inbure-73Research ArticleТЕХНИЧЕСКИЕ НАУКИ. СТРОИТЕЛЬСТВОTECHNICAL SCIENCES. CONSTRUCTIONПроект программного комплекса генерации машин Тьюринга, решающих NP-трудные задачиDraft program complex for generating Turing machines solving NP-hard problemshttps://orcid.org/0000-0003-2659-0355МартьяновВ. И.MartyanovV. I.

Мартьянов Владимир Иванович – доктор физико-математических наук, профессор кафедры автомобильных дорог, Иркутский НИТУ, Байкальский ГУ; Иркутский ГУ.

664074, Иркутск, ул. Лермонтова, 83; 664003, Иркутск, ул. Ленина, 11; 664003, Иркутск, ул. Карла Маркса, 1

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

MartVlIv@mail.ruИркутский национальный исследовательский технический университет; Байкальский государственный университет; Иркутский государственный университетРоссияIrkutsk National Research Technical University; Baikal State University; Irkutsk State UniversityRussian Federation202309112023132285297Copyright © Мартьянов В.И., 20232023Мартьянов В.И.Martyanov V.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inbure.elpub.ru/jour/article/view/73

Целью исследования является обобщение промежуточных результатов программной реализации концепции генерации машин Тьюринга, решающих NP-сложные задачи. Обсуждаются планы по разработке программного пакета для генерации машин Тьюринга, который может стать открытой платформой для обучения студентов теории алгоритмов и информационным технологиям; проведения всеми желающими экспериментов по определению неполиномиальной сложности решения определенной серии задач, сгенерированными машинами Тьюринга; участия всех желающих в генерации машин Тьюринга и решении NP-трудных задач на личных компьютерах; передачи результатов просчетов на платформу, являющуюся подобием генерации криптовалют, но осуществляющую поиск нетленных математических объектов, а не каких-то искусственно созданных на короткий период времени блоков чисел. Отмечается, что идея использования методов удовлетворения ограничениям для генерации машин Тьюринга, решающих NPтрудные задачи, записанные на ленте, является расширением возможностей программирования в ограничениях и, возможно, будет успешной для решения вопроса о равенстве полиномиальной и NP-сложности (P =? NP), что является одной из семи пока не решенных проблем третьего тысячелетия математики.

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.

NP-трудные задачиудовлетворение ограничениямпрограммирование в ограниченияхискусственный интеллектмашины ТьюрингаNP-hard problemssatisfying constraintsprogramming in constraintsartificial intelligenceTuring machinesReferencesМартьянов В.И. NP-трудные задачи: автоматическое доказательство теорем и машины Тьюринга // Baikal Research Journal. 2021. Т.12. № 4. С. 11–20. https://doi.org/10.17150/2411-6262.2021.12(4).11.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.Мартьянов В.И. Логико-эвристические методы сетевого планирования и распознавание ситуаций // Проблемы управления и моделирования в сложных системах. Самара, 2001. С. 209–215.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.).Мартьянов В.И., Архипов В.В., Каташев цев М.Д., Пахомов Д.В. Обзор приложений логико-эвристических методов решения комбинаторных задач высокой сложности // Современные технологии. Системный анализ. Моделирование. 2010. № 4 (28). С. 205–211. EDN: NRBKXP.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.Мартьянов В.И., Сухорутченко В.В., Окунцов В.В. Планирование информационных потоков в иерархической системе // Прикладные системы. М.: ИАП РАН, 1992. С. 46–58.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.).Мартьянов В.И., Вяткин И.В., Могильниц кий Э.Ю. Теоретический и реализационный аспекты некоторых классов задач сетевого управления // Проблемы управления и моделирования в сложных системах. Самара, 1999. С. 203–208.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.).Лагутенков А.В. Криптовалюты. Правила применения // Наука и жизнь. 2018. № 2. С. 22–26.Lagutenkov A.V. Cryptocurrencies. Application rules. Nauka i zhizn'. 2018;2:22-26. (In Russ.).Kharpal A. All you need to know about the top 5 cryptocurrencies // Yahoo! [Электронный ресурс]. URL: https://finance.yahoo.com/news/know-top-5cryptocurrencies-093231173.html (14.03.2023).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].Wilson-Nunn D., Zenil H. On the Complexity and Behaviour of Cryptocurrencies Compared to Other Markets // Research Gate [Электронный ресурс]. URL: https://www.researchgate.net/publication/2680 79329_On_the_Complexity_and_Behaviour_of_Cry ptocurrencies_Compared_to_Other_Markets (14.03.2023).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].Щербина О.А. Удовлетворение ограничений и программирование в ограничениях (препринт). Vienna: University of Vienna, 2012. 118 с.Shcherbina O.A. Udovletvorenie ogranichenii i programmirovanie v ogranicheniyakh (preprint). Vienna: University of Vienna; 2012. 118 p. (In Russ.).Hentenryck van P. Constraint Satisfaction in Logic Programming. Cambridge: The MIT Press, 1989. 356 p.Hentenryck van P. Constraint Satisfaction in Logic Programming. Cambridge: The MIT Press; 1989. 356 p.Стюарт И. Величайшие математические задачи / Пер. с англ. Н. Лисовой. М.: Альпина нонфикшн, 2015. 460 с.Stewart I. The great mathematical problems. Moscow: Al'pina non-fikshn; 2015. 460 p. (In Russ.).Разборов А.А. Алгебраическая сложность. М.: Московский центр непрерывного математического образования, 2016. 32 с.Razborov A.A. Algebraic complexity. Moscow: Moscow Center for Continuing Mathematical Education; 2016. 32 p. (In Russ.).Fortnow L. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton: Princeton University Press, 2013.Fortnow L. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton: Princeton University Press; 2013.Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1965. 392 с.Mal'tsev A.I. Algorithms and recursive functions. Moscow: Nauka; 1965. 392 p.Корольков Ю.Д., Мартьянов В.И. Дискретные модели: представление конечными деревьями и разрешимость формальных теорий. Иркутск: Издво Иркутского национального исследовательского технического университета, 2017. 160 с.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.).Кулик Н.С., Мартьянов В.И., Пахомов Д.В., Большаков Э.А. Проект системы управления региональной сетью автомобильных дорог (СУРАД) Иркутской области // Вестник Иркутского государственного технического университета. 2014. № 4 (87). С. 118–123. EDN: SBNFNJ.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.Кулик Н.С., Мартьянов В.И., Пахомов Д.В. Построение графа автомобильных дорог для системы взимания платы с большегрузного транспорта // Вестник Иркутского государственного технического университета. 2016. № 4 (111). С. 96–101. EDN: VVSOFF. https://doi.org/10.21285/1814-3520-2016-4-96-101.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.Мартьянов В.И., Пахомов Д.В., Архипов В.В. Сетевое планирование содержания сети автомобильных дорог Иркутской области // Новые технологии в инвестиционно-строительной сфере и ЖКХ: сб. науч. трудов: в 2 т. Т. 1. Иркутск: Иркутский государственный технический университет, 2005. С. 123-129.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.).Мартьянов В.И. Теоретико-множественные модели данных в задаче расчета вторичных структур РНК // System Analysis & Mathematical Modeling. 2022. Т. 4. № 4. С. 343–357. EDN: VUNLFX. https://doi.org/10.17150/2713-1734.2022.4(4).343-357.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.Мартьянов В.И., Корольков Ю.Д. Теоретикомножественные модели сложных систем и алгоритмы интеллектуальной поддержки. Иркутск: Изд-во Байкальского государственного университета, 2020. 188 с.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.).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.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.Мартьянов В.И. Теоретико-множественный анализ организации данных учебного процесса и алгоритмы проектирования расписания с элементами искусственного интеллекта // Прикладные проблемы дискретного анализа: сб. науч. тр. 2021. С. 90–100. EDN: BVANFU.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.Leeuwen J.V. Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier, 1998. 1020 p.Leeuwen J.V. Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier, 1998. 1020 p.Knuth D. Postscript about NP-hard problems // ACM SIGACT News. 1974. Vol. 6. No. 2. P. 15– 16. https://doi.org/10.1145/1008304.1008305.Knuth D. Postscript about NP-hard problems. ACM SIGACT News. 1974;6(2):15-16. https://doi.org/10.1145/1008304.1008305.Aaronson S. The Scientific Case for P≠NP // Shtetl-Optimized [Электронный ресурс]. URL: https://scottaaronson.blog/?p=1720 (25.09.2016).Aaronson S. The Scientific Case for P≠NP. Shtetl-Optimized. Available from: https://scottaaronson.blog/?p=1720 (25.09.2016). [Accessed 14th March 2023].Aaronson S. PHYS771 Lecture 6: P, NP, and Friends // Scott Aaronson.ru [Электронный ресурс]. URL: https://www.scottaaronson.com/democritus/lec6.html (25.09.2016).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].Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons, 1985. 75 p.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.Wegener I. Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer, 2005. P. 189. https://doi.org/10.1007/3-540-27477-4.Wegener I. Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer, 2005. P. 189. https://doi.org/10.1007/3-540-27477-4.

The authors declare that there are no conflicts of interest present.