Проект программного комплекса генерации машин Тьюринга, решающих NP-трудные задачи

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

1. Мартьянов В.И. NP-трудные задачи: автоматическое доказательство теорем и машины Тьюринга // Baikal Research Journal. 2021. Т.12. № 4. С. 11–20. https://doi.org/10.17150/2411-6262.2021.12(4).11.

2. Мартьянов В.И. Логико-эвристические методы сетевого планирования и распознавание ситуаций // Проблемы управления и моделирования в сложных системах. Самара, 2001. С. 209–215.

3. Мартьянов В.И., Архипов В.В., Каташев цев М.Д., Пахомов Д.В. Обзор приложений логико-эвристических методов решения комбинаторных задач высокой сложности // Современные технологии. Системный анализ. Моделирование. 2010. № 4 (28). С. 205–211. EDN: NRBKXP.

4. Мартьянов В.И., Сухорутченко В.В., Окунцов В.В. Планирование информационных потоков в иерархической системе // Прикладные системы. М.: ИАП РАН, 1992. С. 46–58.

5. Мартьянов В.И., Вяткин И.В., Могильниц кий Э.Ю. Теоретический и реализационный аспекты некоторых классов задач сетевого управления // Проблемы управления и моделирования в сложных системах. Самара, 1999. С. 203–208.

6. Лагутенков А.В. Криптовалюты. Правила применения // Наука и жизнь. 2018. № 2. С. 22–26.

7. 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).

8. 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).

9. Щербина О.А. Удовлетворение ограничений и программирование в ограничениях (препринт). Vienna: University of Vienna, 2012. 118 с.

10. Hentenryck van P. Constraint Satisfaction in Logic Programming. Cambridge: The MIT Press, 1989. 356 p.

11. Стюарт И. Величайшие математические задачи / Пер. с англ. Н. Лисовой. М.: Альпина нонфикшн, 2015. 460 с.

12. Разборов А.А. Алгебраическая сложность. М.: Московский центр непрерывного математического образования, 2016. 32 с.

13. Fortnow L. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton: Princeton University Press, 2013.

14. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1965. 392 с.

15. Корольков Ю.Д., Мартьянов В.И. Дискретные модели: представление конечными деревьями и разрешимость формальных теорий. Иркутск: Издво Иркутского национального исследовательского технического университета, 2017. 160 с.

16. Кулик Н.С., Мартьянов В.И., Пахомов Д.В., Большаков Э.А. Проект системы управления региональной сетью автомобильных дорог (СУРАД) Иркутской области // Вестник Иркутского государственного технического университета. 2014. № 4 (87). С. 118–123. EDN: SBNFNJ.

17. Кулик Н.С., Мартьянов В.И., Пахомов Д.В. Построение графа автомобильных дорог для системы взимания платы с большегрузного транспорта // Вестник Иркутского государственного технического университета. 2016. № 4 (111). С. 96–101. EDN: VVSOFF. https://doi.org/10.21285/1814-3520-2016-4-96-101.

18. Мартьянов В.И., Пахомов Д.В., Архипов В.В. Сетевое планирование содержания сети автомобильных дорог Иркутской области // Новые технологии в инвестиционно-строительной сфере и ЖКХ: сб. науч. трудов: в 2 т. Т. 1. Иркутск: Иркутский государственный технический университет, 2005. С. 123-129.

19. Мартьянов В.И. Теоретико-множественные модели данных в задаче расчета вторичных структур РНК // System Analysis & Mathematical Modeling. 2022. Т. 4. № 4. С. 343–357. EDN: VUNLFX. https://doi.org/10.17150/2713-1734.2022.4(4).343-357.

20. Мартьянов В.И., Корольков Ю.Д. Теоретикомножественные модели сложных систем и алгоритмы интеллектуальной поддержки. Иркутск: Изд-во Байкальского государственного университета, 2020. 188 с.

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. Мартьянов В.И. Теоретико-множественный анализ организации данных учебного процесса и алгоритмы проектирования расписания с элементами искусственного интеллекта // Прикладные проблемы дискретного анализа: сб. науч. тр. 2021. С. 90–100. 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. Vol. 6. No. 2. P. 15– 16. https://doi.org/10.1145/1008304.1008305.

25. Aaronson S. The Scientific Case for P≠NP // Shtetl-Optimized [Электронный ресурс]. URL: https://scottaaronson.blog/?p=1720 (25.09.2016).

26. Aaronson S. PHYS771 Lecture 6: P, NP, and Friends // Scott Aaronson.ru [Электронный ресурс]. URL: https://www.scottaaronson.com/democritus/lec6.html (25.09.2016).

27. 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.

28. Wegener I. Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer, 2005. P. 189. https://doi.org/10.1007/3-540-27477-4.