Российский математик представил метод решения одной из семи "Задач Тысячелетия".

Сотрудник иппи ран Александр жуланов предложил новый способ решать симметричную задачу коммивояжера - поиск самого короткого замкнутого маршрута через все заданные точки без повторных посещений. Работа в журнале "Информационные Процессы опубликована".

Эта задача относится к классу NP - трудных: найденный маршрут легко проверить, но быстро отыскать лучший для большого числа точек крайне сложно. Только в том случае, если алгоритм жуланова действительно решает ее за время, которое растет не слишком быстро с увеличением числа точек, это могло бы стать доказательством равенства классов P и NP.

Проблема P против NP входит в список семи "Задач Тысячелетия" математического института клея. За строго доказанное решение каждой обещан миллион долларов. Пока подтверждена лишь гипотеза пуанкаре, доказанная Григорием Перельманом.

Метод жуланова имитирует распространение сигналов из вершин графа и поэтапно отбрасывает маршруты, которые заведомо не могут быть кратчайшими. Автор предоставил программный код, поэтому другие математики смогут проверить алгоритм и заявленные характеристики.

В иппи ран подчеркивают: публикация статьи еще не означает решения задачи тысячелетия. Доказательство должно независимую экспертную проверку пройти. В случае если оно подтвердится, подход может пригодиться в логистике, ИИ и разработке новых молекул. Иллюстрация: Chatgpt.