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