Все статьи подряд / Математика / Хабр's Journal

Тот же граф, только в другой руке?

В 2015 году математик Ласло Бабай представил свой более эффективный алгоритм, решающий задачу изоморфизма графов (Graph Isomorphism, GI) за квазиполиномиальное время. На Хабре даже есть статья, освещающая это событие. Однако в дальнейшем сам учёный признал некоторую ошибочность своего подхода, что всё равно не повлияло на отношение большинства математиков к его открытию, поскольку даже получившийся вариант, решающий задачу за субэкспоненциальное время, оказался эффективнее существующих алгоритмов. Тем не менее учёный не остановился на этом и обнаружил ошибку. Опубликованные исправления алгоритма всё-таки привели к решению задачи изоморфизма за квазиполиномиальное время.

Проблема изоморфизма графов требует алгоритмов, которые могут определить, являются ли два графа структурно идентичными. На протяжении десятилетий эта задача занимала особый статус как одна из немногих естественно возникающих задач, уровень сложности которых трудно определить. Многие годы исследователи пытались выяснить, к чему она относится. Даже сейчас неизвестно, к какому классу относится задача, а абстрактно задачу рассматривают как нечто среднее — сложнее, чем P, но легче NP. Задачу из теории графов можно обобщить до общей проблемы изоморфизма, в смежных областях математики существуют идентичные задачи, например изоморфизм конечных групп.