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

в 23:12, , рубрики: Занимательные задачки, изоморфизм графов, класс NP, класс P, математика, теоретическая информатика, теория сложности вычислений, метки:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автор: alizar

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js