Опубликован быстрый алгоритм для задачи изоморфизма графов

Эти два графа являются изоморфными

Математик Ласло Бабай (László Babai) с факультета компьютерных наук и математики Чикагского университета представил быстрый новый алгоритм для решения задачи изоморфизма графов ^[1] — одной из фундаментальных проблем теории сложности вычислений. Алгоритм приводит проблему очень близко к классу P. По мнению ^[2] некоторых специалистов, это один из самых значительных результатов в теоретической информатике за десятилетие, если не за несколько десятилетий.

О создании алгоритма Ласло объявил ^[3] месяц назад. По его словам, алгоритм значительно эффективнее, чем самый лучший из существующих ^[4], который был рекордсменом более тридцати лет: его разработал ныне профессор Юджин Люкс в 1983 году, тот решал задачу за субэкспоненциальное время.

Ласло Бабаю, судя по всему, удалось практически свести проблему к задаче класса P: его алгоритм заявлен как вычисляемый в квази-полиномиальное время.

11 декабря 2015 года статья с описанием нового алгоритма наконец-то опубликована ^[5] в открытом доступе, а также отправлена в Ассоциацию по вычислительной технике. Официальная презентация алголритма состоится на 48-м симпозиуме по теории вычислений ^[6].

В течение нескольких десятилетий проблема изоморфизма графов имела особый статус в теории сложности вычислений. В то время как сотни других задач смиренно поддавались классификации по классу P или классу NP, проблему изоморфизма графов никак не могли однозначно классифицировать. Она казалась сложнее, чем лёгкие задачи и легче, чем сложные, занимая уникальное положение как будто между двумя классами задач. Это одна из двух знаменитых задач в этой странной промежуточной области, говорит ^[2] Скотт Ааронсон (Scott Aaronson), математик из Массачусетского технологического института. Теперь, по его словам «похоже, что одна из двух сдалась».

Вторая общеизвестная задача из «серой» области — факторизация целых чисел.

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

Ласло Бабай представляет свой алгоритм для решения задачи изоморфизма графов 10 ноября 2015 года в Чикагском университете

Алгоритм Ласло Бабая работает путём виртуального «окрашивания» вершин графа. Сначала случайным образом выбираются несколько вершин, они «окрашиваются» в разные цвета. Затем выбираются несколько вершин во втором графе, предположительно соответствующих вершинам из первого графа, им присваиваются те же цвета. В конце концов, перебираются все варианты. После первоначального выбора алгоритм окрашивает на обоих графах предположительно изоморфные вершины, соседствующие с первоначально выбранными, в другие цвета до тех пор, пока не остаётся связей между вершинами.

Если алгоритм Бабая пройдёт проверку коллег, то это самое значительное открытие в данном разделе математики за последнее время. «До его объявления вряд ли кто-то, кроме, может быть, его самого, предполагал появление такого результата в ближайшие десять лет, если вообще когда-либо», — говорит Джошуа Грочоу (Joshua Grochow) из института Санта-Фе.

За последние несколько недель Бабай дал несколько лекций с изложением своего алгоритма. Видеозапись первой лекции от 10 ноября представлена ниже.

Задача изоморфизма графов считается «универсальной», то есть к ней можно свести любую проблему, где ставится вопрос об изоморфизме комбинаторных структур. Обычно такая «универсальность» свойственна задачам класса NP. В то же время задача изоморфизма графов демонстрировала одно странное свойство, которого нет ни у одной NP-полной задачи: прохождение «слепого теста» (протокол Артура-Мерлина ^[7]).

В 2012 году неформальный опрос ^[8] учёных в области теоретической информатики дал такой результат: 14 из них высказались, что проблема изоморфизма графов принадлежит к классу P, а шестеро сказали, что не принадлежит. До объявления Ласло Бабая мало кто думал, что задачу решат когда-нибудь в ближайшее время. «Я думал, что может она принадлежит к классу P, а может быть нет, но при моей жизни этого никто не узнает», — признался Грочоу.

Ласло Бабай работал над проблемой изоморфизма графов почти 40 лет.

Автор: alizar

Источник ^[9]