![](https://habrastorage.org/files/786/5bc/dcb/7865bcdcbf764b07a61a011d14666e94.png)
Эти два графа являются изоморфными
Математик Ласло Бабай (Laszlo Babai) с факультета компьютерных наук и математики Чикагского университета представил быстрый новый алгоритм для решения задачи изоморфизма графов — одной из фундаментальных проблем теории сложности вычислений. Алгоритм приводит проблему очень близко к классу P. По мнению некоторых специалистов, это один из самых значительных результатов в теоретической информатике за десятилетие, если не за несколько десятилетий.
О создании алгоритма Ласло объявил месяц назад. По его словам, алгоритм значительно эффективнее, чем самый лучший из существующих, который был рекордсменом более тридцати лет: его разработал ныне профессор Юджин Люкс в 1983 году, тот решал задачу за субэкспоненциальное время.
Ласло Бабаю, судя по всему, удалось практически свести проблему к задаче класса P: его алгоритм заявлен как вычисляемый в квази-полиномиальное время.
11 декабря 2015 года статья с описанием нового алгоритма наконец-то опубликована в открытом доступе, а также отправлена в Ассоциацию по вычислительной технике. Официальная презентация алголритма состоится на 48-м симпозиуме по теории вычислений.
В течение нескольких десятилетий проблема изоморфизма графов имела особый статус в теории сложности вычислений. В то время как сотни других задач смиренно поддавались классификации по классу P или классу NP, проблему изоморфизма графов никак не могли однозначно классифицировать. Она казалась сложнее, чем лёгкие задачи и легче, чем сложные, занимая уникальное положение как будто между двумя классами задач. Это одна из двух знаменитых задач в этой странной промежуточной области, говорит Скотт Ааронсон (Scott Aaronson), математик из Массачусетского технологического института. Теперь, по его словам «похоже, что одна из двух сдалась».
Вторая общеизвестная задача из «серой» области — факторизация целых чисел.
Задача изоморфизма графов сама по себе выглядит просто: нужно определить, являются два графа изоморфными, то есть можно ли простым передвижением вершин трансформировать один граф в другой, сохраняя связи между вершинами. Вот и всё. Несмотря на кажущуюся простоту, эту задачу трудно решить, потому что даже маленькие графы могут принимать множество разнообразных форм.
![](https://habrastorage.org/files/f34/6fe/27a/f346fe27aab744cb87854188c62c8f02.jpg)
Ласло Бабай представляет свой алгоритм для решения задачи изоморфизма графов 10 ноября 2015 года в Чикагском университете
Алгоритм Ласло Бабая работает путём виртуального «окрашивания» вершин графа. Сначала случайным образом выбираются несколько вершин, они «окрашиваются» в разные цвета. Затем выбираются несколько вершин во втором графе, предположительно соответствующих вершинам из первого графа, им присваиваются те же цвета. В конце концов, перебираются все варианты. После первоначального выбора алгоритм окрашивает на обоих графах предположительно изоморфные вершины, соседствующие с первоначально выбранными, в другие цвета до тех пор, пока не остаётся связей между вершинами.
Если алгоритм Бабая пройдёт проверку коллег, то это самое значительное открытие в данном разделе математики за последнее время. «До его объявления вряд ли кто-то, кроме, может быть, его самого, предполагал появление такого результата в ближайшие десять лет, если вообще когда-либо», — говорит Джошуа Грочоу (Joshua Grochow) из института Санта-Фе.
За последние несколько недель Бабай дал несколько лекций с изложением своего алгоритма. Видеозапись первой лекции от 10 ноября представлена ниже.
Задача изоморфизма графов считается «универсальной», то есть к ней можно свести любую проблему, где ставится вопрос об изоморфизме комбинаторных структур. Обычно такая «универсальность» свойственна задачам класса NP. В то же время задача изоморфизма графов демонстрировала одно странное свойство, которого нет ни у одной NP-полной задачи: прохождение «слепого теста» (протокол Артура-Мерлина).
В 2012 году неформальный опрос учёных в области теоретической информатики дал такой результат: 14 из них высказались, что проблема изоморфизма графов принадлежит к классу P, а шестеро сказали, что не принадлежит. До объявления Ласло Бабая мало кто думал, что задачу решат когда-нибудь в ближайшее время. «Я думал, что может она принадлежит к классу P, а может быть нет, но при моей жизни этого никто не узнает», — признался Грочоу.
Ласло Бабай работал над проблемой изоморфизма графов почти 40 лет.
Комментарии (24)
QtRoS
16.12.2015 09:44+2Алгоритм Ласло Бабая работает путём виртуального «окрашивания» вершин графа. Сначала случайным образом выбираются несколько вершин, они «окрашиваются» в разные цвета. Затем выбираются несколько вершин во втором графе, предположительно соответствующих вершинам из первого графа, им присваиваются те же цвета. В конце концов, перебираются все варианты. После первоначального выбора алгоритм окрашивает на обоих графах предположительно изоморфные вершины, соседствующие с первоначально выбранными, в другие цвета до тех пор, пока не остаётся связей между вершинами.
Но ведь идея крайне простая, где за этими словами кроется трюк? Или это из-за перевода?Mrrl
16.12.2015 10:16+12«предположительно изоморфные вершины». Почему именно эти вершины «предположительно изоморфны», где гарантия, что мы ничего не потеряем, и при этом не уйдём в комбинаторный взрыв? И что при неудаче получим доказательство, что графы неизоморфны?
Nashev
17.12.2015 10:04Вот тоже пришёл в комменты за этим вопросом. Это ж тупой перебор в лоб, если выкинуть мистику слова «предположительно» и брать всё подряд, отказываясь от гипотезы при обломе, и начиная проверять другую. Единственно, могу предположить что новизна в том, что впервые кто-то проанализировал этот алгоритм на P/NP-полноту
mihaild
17.12.2015 18:24-1Что такое «P/NP полнота»? (что такое P-полнота знаю, что такое NP-полнота знаю, что такое P/NP полнота — не знаю)
И что такое анализ алгоритма на нее? (что такое анализ алгоритма на P полноту — не знаю, что такое анализ алгоритма на NP полноту — не знаю)
А новизна в том, что предложен алгоритм, работающий быстрее чем всё, что было известно раньше.
PsyHaSTe
22.12.2015 10:18Есть мнение, что большинство реально крутых алгоритмов простые. И чем проще, тем круче :) Равно как и простое объяснение как правило вернее сложного (из истории можно припомнить хотя бы те же эпициклы против объяснения Коперника)
avsmal
22.12.2015 17:34Настолько простая, что потребовалось три лекции, чтоб её объяснить =)
Только если эту идею применить в лоб, то получится экспоненциальный алгоритм.
Это ооочень поверхностное описание одной из идей, которые в этом алгоритме используются.
Почитайте, например, тут: rjlipton.wordpress.com/2015/11/21/a-little-more-on-the-graph-isomorphism-algorithmNashev
25.12.2015 00:55Вы разобрались, в чём фишка? Можете пересказать?
avsmal
25.12.2015 03:03Насколько я понимаю, там нет какой-то «фишки», по которой можно понять так сразу как алгоритм работает. Это сложный алгоритм с очень сложным анализом. Сейчас объяснение основных идей алгоритма и оценки его времени работы занимает три лекции для хорошо подготовленной аудитории. Для этого нужен определённый бекграунд, необходимо понимать, что это за задача, и какие есть проблемы на пути к её решению. В CS клубе был соответствующий курс: old.compsciclub.ru/courses/graphisomorphism
Но для понимания алгоритма этого недостаточно — нужно намного больше знаний и в т.ч. очень хорошее понимание алгебры.
Можете для интереса глянуть в статью: arxiv.org/pdf/1512.03547v1.pdf
Если не готовы читать оригинал, то смотрите обзорные статьи вроде этой:
jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details
lostmsu
А для каких практических задач нужно решение этой проблемы? Список в википедии довольно короткий и не подробный.
DoctorChaos
Вы ждете ответа от ализара? Он хорошо если сам хотя бы половину слов из этой статьи понимает)
Ализар, может, вам на гиктаймсе все-таки жить? Так хорошо тут было без ваших «сенсаций».
Scratch
Мне бы такая штука пригодилась когда я писал диплом по триангуляции поверхностей. А так, написали же, что многие комбинаторные задачи сводятся к графам
Mrrl
Чаще нужна ещё более общая задача — найти в графе A фрагмент, изоморфный графу B. Может быть очень полезна в компьютерном зрении, в задачах совмещения изображений и сцен (особенно с нелинейными искажениями), распознавании объекта по топологической схеме… Про поиски фрагментов программ и схем для оптимизации и прочего уже писали.
netmaxed
а есть, кстати, что-нибудь интересное на этом поприще? какие-нибудь прорывы?
Mrrl
Понятия не имею. Когда мне нужно что-то подобное, я пишу очередной велосипед. Пока лучше всего работает алгоритм с использованием матриц, в которых вычисляется вероятность соответствия для каждой пары вершин — но я уже забыл, откуда он взялся и как называется.
mihaild
А вот это уже NP-полная задача.
И даже проверка наличия полного подграфа из k вершин тоже np полна.
knagaev
Дополню, если позволите.
Алгоритмы работы с графами сейчас в большинстве популярных случаев применяются в обработке данных соцсетей.
И Вы абсолютно правы — это фактически подзадача для задачи поиска паттерна в графе.
Поиск паттерна практически можно отнести к классу «почти универсальных» методов обработки связанных данных.
А статья (точнее новость, в ней упомянутая) мне показалась интересной, хоть Ализар и считается любителем «скандалов, интриг, расследований».
0xd34df00d
Компьютерная алгебра, оптимизация символьных выражений.
Что приятно, там вылезают всячкие интересные категориальные объекты вроде копроизведения в категории графов.
Mrrl
Но там ориентированные графы, да ещё и ациклические. Может быть, для них эта задача проще?
0xd34df00d
Если я правильно помню, то простоты из этого особой извлечь не удаётся. Но я могу помнить неправильно — так, почитал немножко книг и статей, когда раздумывал о том, делать связанные с этим вещи частью дипломной работы или нет.
Mrrl
Действительно. Задача о неориентируемых графах элементарно сводится к ориентируемым ациклическим, с утроенным числом вершин (на всякий случай, чтобы думать меньше).
yorko
Есть еще одно приложение, где часто возникает необходимость проверки изоморфизма подграфу (задача NP-полна) — машинное обучение на графах. Успешнее всего применяется в химинформатике при анализе зависимости типа «структура-свойство» (QSAR). Обучающая выборка может выглядеть так: молекулярные графы этих веществ — положительные объекты (обладают свойством, например, токсичностью, канцерогенностью, мутагенностью и т.д.), молекулярные графы других веществ — отрицательные объекты (то есть вешества соот-но не токсичны, не канцерогенны, не мутагенны). Самая простая идея — настроить подграфы всех обучающих графов и представить каждый граф бинарным вектором, где 1 стоит там, где соответствующий «маленький» граф изоморфен подграфу обучающейго графа. (Банальный пример: помеченные графы A-B-C и B-C-D представятся векторами [1,1,1,0,1,1,0] и [0,1,1,1,0,1,1], в признаковом пространстве подграфов [A, B, C, D, A-B, B-C, C-D]). Вычислительная сложность такого представления очень высокая, потому что подграфов очень много, а также много раз необходимо проверять изоморфизм подграфу. Тем не менее, GBoost работает именно так — это «обычный» бустинг вот в таком признаковом пространстве подграфов, где «деревянным» методом важности признаков определяются важные для классифкации подграфы (их потом можно принести и показать эксперту, и он скажет, что да, например, такой подграф — бензольное кольцо — действительно свидетельствует о таком-то свойстве вещества).
Но state-of-the-art в классификации графовых данных — это ядерные методы, в большинстве из которых все равно надо часто проверять изоморфизм подграфу.
Hypuk
Тут больше теоретическая важность — уменьшилось количество задач в NP-intermediate кандидатах.
Сложность алгоритма квази-полиномиальная и особого значения в «реальном» мире иметь не будет. Сам Бабай в одной из лекций говорил что существующие эвристические и вероятностные алгоритмы более полезны для реальных задач.
BalinTomsk
поиск рож по базе, поиск генов по базе днк