Омские научные чтения - Математика

О вычислительной сложности задачи проверки изоморфизма графов (обзор результатов)

В докладе рассматриваются наиболее известные подходы к решению задачи проверки

изоморфизма графов. Приводятся результаты, характеризующие вычислительную

сложность этих подходов. Вопрос о том, принадлежит ли при принятии гипотезы

$P\neq NP$ задача проверки изоморфизма графов к классу полиномиально разрешимых

задач $P$ или является $NP$-трудной задачей, остаётся открытым. Большинство

исследователей в этой области склонны считать, что задача имеет некоторую

промежуточную вычислительную сложность. Рассматривается работа Л. Бабаи

об алгоритме решения задачи проверки изоморфизма графов, имеющем, в соответствии

с доказываемом в этой работе утверждением, квазиполиномиальную вычислительную

сложность, и рассматриваются следствия, получаемые из этого утверждения.

Ключевые слова: изоморфизм графов, вычислительная сложность.

Текст доклада

Вопросы отсутствуют