Эти два графа являются изоморфными
Математик Ласло Бабай (Laszlo Babai) с факультета компьютерных наук и математики Чикагского университета представил быстрый новый алгоритм для решения задачи изоморфизма графов — одной из фундаментальных проблем теории сложности вычислений. Алгоритм приводит проблему очень близко к классу P. По мнению некоторых специалистов, это один из самых значительных результатов в теоретической информатике за десятилетие, если не за несколько десятилетий.
О создании алгоритма Ласло объявил месяц назад. По его словам, алгоритм значительно эффективнее, чем самый лучший из существующих, который был рекордсменом более тридцати лет: его разработал ныне профессор Юджин Люкс в 1983 году, тот решал задачу за субэкспоненциальное время.
Ласло Бабаю, судя по всему, удалось практически свести проблему к задаче класса P: его алгоритм заявлен как вычисляемый в квази-полиномиальное время.
11 декабря 2015 года статья с описанием нового алгоритма наконец-то опубликована в открытом доступе, а также отправлена в Ассоциацию по вычислительной технике. Официальная презентация алголритма состоится на 48-м симпозиуме по теории вычислений.
В течение нескольких десятилетий проблема изоморфизма графов имела особый статус в теории сложности вычислений. В то время как сотни других задач смиренно поддавались классификации по классу P или классу NP, проблему изоморфизма графов никак не могли однозначно классифицировать. Она казалась сложнее, чем лёгкие задачи и легче, чем сложные, занимая уникальное положение как будто между двумя классами задач. Это одна из двух знаменитых задач в этой странной промежуточной области, говорит Скотт Ааронсон (Scott Aaronson), математик из Массачусетского технологического института. Теперь, по его словам «похоже, что одна из двух сдалась».
Вторая общеизвестная задача из «серой» области — факторизация целых чисел.
Задача изоморфизма графов сама по себе выглядит просто: нужно определить, являются два графа изоморфными, то есть можно ли простым передвижением вершин трансформировать один граф в другой, сохраняя связи между вершинами. Вот и всё. Несмотря на кажущуюся простоту, эту задачу трудно решить, потому что даже маленькие графы могут принимать множество разнообразных форм.
Ласло Бабай представляет свой алгоритм для решения задачи изоморфизма графов 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
поиск рож по базе, поиск генов по базе днк