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