Информационное агентство ТАСС обратило внимание на работу Александра Жуланова, опубликованную в академическом журнале института «Информационные процессы».

Исследование посвящено симметричной задаче коммивояжера (TSP) — одной из ключевых NP-трудных проблем. Согласно теореме Кука-Левина, нахождение ее полиномиального решения напрямую связано с вопросом равенства классов сложности P и NP, входящим в список семи «задач тысячелетия» Математического института Клея.

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

В случае подтверждения корректности метода предложенный подход откроет широкие возможности для практики: от оптимизации сложных логистических сетей и синтеза новых молекул до развития систем «объяснимого ИИ».

Прочесть статью ТАСС можно по ссылке.