Российский учёный Александр Жуланов предложил новый подход к одной из семи «задач тысячелетия» — проблеме P против NP. Сейчас математики пытаются понять, можно ли сложную задачу решить так же быстро, как проверить уже готовый ответ. Работа Жуланова опубликована в научном журнале «Информационные процессы» Института проблем передачи информации РАН.
«Задачами тысячелетия» называют семь важнейших математических проблем, которые Математический институт Клэя сформулировал в 2000 году. За решение каждой из них назначена премия в 1 млн долларов. В список входят гипотезы Римана, Ходжа и Берча — Свиннертона — Дайера, проблема P против NP, уравнения Навье — Стокса, теория Янга — Миллса и гипотеза Пуанкаре. Последнюю в итоге доказал Григорий Перельман, а остальные шесть официально до сих пор считаются нерешёнными.
Работа Жуланова посвящена проблеме P против NP и связана с так называемой симметричной задачей коммивояжёра. В ней нужно найти самый короткий замкнутый маршрут между заданными пунктами так, чтобы каждый пункт был посещён ровно один раз.
Эта задача относится к классу NP-трудных. Поэтому существование точного алгоритма, который решал бы её общий случай за полиномиальное время, означало бы равенство P и NP.
Предложенный учёным метод основан на динамическом моделировании сигналов, которые одновременно распространяются от всех вершин графа. Алгоритм анализирует порядок посещения этих вершин и постепенно отбрасывает маршруты, которые не могут оказаться самыми короткими.
В ИППИ РАН подчёркивают, что сама публикация статьи не означает решения проблемы P против NP. Специалистам ещё предстоит проверить математическое доказательство, поискать возможные контрпримеры и убедиться, что алгоритм корректно работает для любых допустимых исходных данных.
При этом результаты уже можно проверять независимо. Автор предоставил программный код, который позволяет математикам провести аудит и проверить заявленные временные характеристики алгоритма на практике.
Если правильность метода подтвердится, он может найти применение в оптимизации сложных логистических сетей, создании новых молекул и развитии систем искусственного интеллекта. В частности, по словам главного научного сотрудника ИППИ РАН Дмитрия Репина, алгоритм потенциально может помочь создавать «объяснимый ИИ», который будет допускать меньше ошибок и «галлюцинаций» нейросетей.