Последствия квазиполиномиального алгоритма времени для задачи об изоморфизме графа

40

Проблема изоморфизма графов (GI), возможно, является наиболее известным кандидатом в NP-промежуточную задачу. Самый известный алгоритм - это субэкспоненциальный алгоритм с временем выполнения . Известно, что GI не является -полным, если не разрушится полиномиальная иерархия .NP2O(nlogn)Nп

Каковы будут теоретические последствия сложности алгоритма квазиполиномиального времени для задачи об изоморфизме графа?
Будет ли квазиполиномиальный алгоритм времени для GI опровергать какие-либо известные гипотезы в теории сложности?


Другие аналогичные проблемы, такие как минимальное доминирующее множество в задаче о турнирах, проблема изоморфизма групп и проблема изоморфизма турниров, имеют алгоритмы квазиполиномиального времени ( QP ). Последние две проблемы сводятся за полиномиальное время к GI.

Можем ли мы эффективно уменьшить проблему минимального доминирующего множества в турнирах до GI?
Есть ли какие-либо предположения о том, что GI трудно для QP?

Обновление (2015-12-14) : Бабаи опубликовал предварительный черновик статьи по arXiv для своего алгоритма квазиполиномиального времени для GI.

Обновление (2017-01-04) : Бабай отказался от утверждения, что алгоритм находится в квазиполиномиальном времени, согласно новому анализу, алгоритм находится в субэкспоненциальном времени который находится внутри .2 n o ( 1 )ехрехр(О~(Л.Г.N))2Nо(1)

Обновление (2017-01-09) : Бабаи восстановил квазиполиномиальное требование о времени, заменив нарушающую процедуру более эффективной.

Мухаммед Аль-Туркистани
источник
6
Я думаю, что многие люди думают, что он имеет алгоритм полиномиального времени, и AFAIK такой алгоритм не будет иметь каких-либо теоретических последствий сложности.
Гек Беннетт
7
Это не совсем то, о чем вы просите, но это лучшее, что я знаю: групповой изоморфизм обладает естественным и простым алгоритмом квазиполиномиального времени, но, очевидно, нет снижения с GI до GroupIso: eccc. hpi-web.de/report/2010/117 . Формально более простой вопрос, чем тот, который вы задаете, но все еще широко открытый, состоит в том, чтобы доказать, что не происходит сокращения времени по времени от GI до GroupIso. AC0
Джошуа Грохув
14
Я думаю, что через два года у нас есть ответ. Ласло Бабай доказал, что GI имеет квазиполиномиальный алгоритм времени. Источник: lucatrevisan.wordpress.com/2015/11/03/…
user3415207
8
@ user3415207 Бабай отказался от требования квазиполиномиального времени выполнения . Видимо была ошибка в анализе.
Рафаэль
6
@ Рафаэль ... и Бабай восстановил свои права (та же ссылка, что и у тебя).
Дэнни

Ответы:

5

Насколько я могу судить, если вы просто спросите о последствиях самого факта (в виде черного ящика), что GI находится в QP, я думаю, что ответ будет очень небольшим. Единственное, о чем я могу думать, это не теорема, а следствие для направлений исследований, это групповой изоморфизм. Поскольку GroupIso сводится к GI, и мы даже не знаем, находится ли GroupIso в P, размещение GroupIso в P можно рассматривать как важное препятствие для помещения GI в P (если вы думаете, что последнее может иметь место).

Однако, поскольку тривиальным алгоритмом для GroupIso является , тогда, когда сложность GI была на уровне 2 ˜ O ( NжурналN+О(1), нам пришлось пройти долгий путь в улучшении сложности GI, прежде чем GroupIso сталнепосредственным существеннымпрепятствием для введения GI в P. Но если GI находится в QP, то GroupIso становится гораздо более значимым препятствием для дальнейшего улучшения GI. (Конечно, показатель степени в квазиполиноме все еще является потенциально значимым разрывом, но разрыв становитсянамногоменьше, когда GI находится в QP.)2О~(N)

Джошуа Грохов
источник
Похоже, что мы не можем улучшить более слабую верхнюю границу проверки изоморфизма проективных плоскостей ( ). См. Cstheory.stackexchange.com/questions/34773/…NО(журналжурналN)
Мохаммед Аль-Туркистани
@ MohammadAl-Turkistany: Да, но тогда применим мой тот же аргумент: если GI «идет» в квазиполии, то ProjPlaneIso очень далек от того, чтобы препятствовать введению GI в P. Когда GI вовремя для некоторого c , тогда ProjPlaneIso станет существенным препятствием. Таким образом, в данный момент может показаться, что GroupIso является более непосредственным препятствием - возможно, когда-нибудь ProjPlaneIso будет ...NО(журналжурналN)сс
Джошуа
@JoshuaGrochow Согласитесь ли вы со мной, что подход Франсуа Ле Галля и Дэвида Дж. Розенбаума в « О проблемах изоморфизма групп и цвета» имеет смысл? Или, по крайней мере, они рассматривают некоторые вопросы, которые могут возникнуть после получения базового понимания результатов Ласло Бабая?
Томас Климпел
@ThomasKlimpel: Я согласен, что их статья имеет смысл, хотя я пока не вижу, как воспользоваться их идеями (несмотря на понимание большинства доказательств Бабая).
Джошуа
Разве вы не верите, что GI в QP в конечном итоге приведет к помещению GI в ограниченный класс недетерминизма, такой как ? βКп
Мохаммед Аль-Туркистани
2

Относительно последнего вопроса: теорема иерархии времени сразу подразумевает, что QP не имеет полных проблем при многочленном или многочленовом редукциях за полиномиальное время. (С другой стороны, каждая задача, кроме save и Σ , QP-трудна при квазиполиномиальных редукциях.) Таким образом, предполагая, что результат Бабая верен, GI не QP-сложен.Σ*

Эмиль Йержабек поддерживает Монику
источник
0

Каковы будут теоретические последствия сложности алгоритма квазиполиномиального времени для задачи об изоморфизме графа?

Более или менее похожи на последствия алгоритма детерминированного полиномиального времени для тестирования простоты, алгоритма детерминированного полиномиального времени для линейного программирования и другого случая, когда были известны практически эффективные (рандомизированные) алгоритмы (с редкими патологическими примерами, когда алгоритм стал неэффективным) и используется в течение длительного времени. Это подтверждает гипотезу о том, что практическая эффективность является хорошим показателем существования детерминированных теоретических алгоритмов, преодолевающих проблемы редких патологических примеров.

Будет ли квазиполиномиальный алгоритм времени для GI опровергать какие-либо известные гипотезы в теории сложности?

Нет, предположения скорее идут в противоположную сторону, а именно, что GI находится в P. Так как GI находится в NP, будет невозможно опровергнуть этот тип предположения в ближайшее время.

Можем ли мы эффективно уменьшить проблему минимального доминирующего множества в турнирах до GI?

Минимальное доминирующее множество не является проблемой изоморфизма, поэтому нет никаких причин, по которым его следует приводить к GI.

Есть ли какие-либо предположения о том, что GI трудно для QP?

Мы даже не знаем, как свести проблему изоморфизма строк к GI, и это, по крайней мере, проблема изоморфизма. Доказательство Бабая показало, что в QP был изоморфизм струн, так что ... А что для QP трудно даже предполагать? Тяжело при полиномиальном сокращении времени?


Из введения Франсуа Ле Галля и Дэвида Дж. Розенбаума "О проблемах группового и изоморфизма цвета"

Сложность задач проверки изоморфизма заслуживает изучения, поскольку они являются фундаментальными вычислительными вопросами, а также потому, что многие из них, как известно, не находятся в P, но, тем не менее, кажутся более простыми, чем NP-полные задачи. Наиболее изученным из них является проблема изоморфизма графов.

гя*гря*определены (в вышеупомянутой статье, но авторы справедливо задаются вопросом, почему никто не делал этого раньше), которые добавляют недостающие фрагменты из проблемы изоморфизма строк. (А проблема изоморфизма цвета - это просто другое название проблемы изоморфизма строки. Проблема автоморфизма цвета имени восходит к первоначальным работам Бабая и Лукса, изоморфизм строки имени встречается позже в их статье о канонической маркировке.)

гя*


Изменить: Этот ответ был дан в контексте отказа от результата Бабая, прежде чем он объявил исправление. Это говорит о том, что небольшое обобщение проблемы изоморфизма графов, предложенной проблемой изоморфизма струн, является действительно важной проблемой. Здесь подразумевается, что любой разумный алгоритм для задачи об изоморфизме графа приведет к аналогичному алгоритму для обобщенной задачи об изоморфизме графа. Обобщенная задача полиномиально время эквивалентна задача множества стабилизатора , то проблема пересечения группы , задача смежного класса пересечения, то проблема набора Транспортера ... Идея этого ожидания в том , что обобщенная проблема будет возникать в рекурсивной частилюбого разумного алгоритма, поэтому он должен быть решен в любом случае. (И вполне возможно, что обобщенная задача за полиномиальное время эквивалентна изоморфизму графа.)

Теперь комментарии Джошуа Грохоу показывают, что мне не удалось объяснить концептуальную важность недостающих фрагментов из проблемы изоморфизма строк. Для бесконечных структур может быть легче понять, что действительный изоморфизм должен не только сохранять данную структуру, но также принадлежать к соответствующей категории функций (например, категории непрерывных функций). Для конечных структур аналогичное явление в основном имеет место для фактор-структур, где соответствующая категория функций должна быть совместима с данными коэффициентами. Материал Джонсона является типичным примером таких отношений, например, логика разбиения работает над двумя подмножествами элементов некоторого базового набора. Также обратите внимание, что ограничение допустимой категории для изоморфизмов часто облегчает задачу проверки изоморфизма,

Проблема с обобщениями проблемы изоморфизма графа состоит в том, где остановиться. Почему бы не обобщить настолько, чтобы охватить проблему изоморфизма групп перестановок? Этот вопрос действительно сложен, так как многие нетривиальные результаты для изоморфизма графов, вероятно, перенесут и на изоморфизм групп перестановок. Но здесь представляется более разумным рассматривать теорию групп вычислительных перестановок как отдельный предмет, даже если она действительно имеет тесную связь с проблемой изоморфизма графов.

Томас Климпел
источник
1
SN
1
@JoshuaGrochow Для цвета iso цвета - это просто произвольные числа (wlog ограничен [n]). Для строки iso строки даны по фиксированному конечному алфавиту. Я думал, что это был двоичный алфавит, но я неправильно это запомнил. Я только что вспомнил, что изначально был озадачен тем, что цвет iso - это просто другое название для строки iso. Поэтому, когда я решил прочитать эту газету после того, как Ласло отозвал его заявление, мне показалось, что это не так. Может быть, это действительно разница, потому что "через конечный алфавит" сообщается "исправь свой любимый конечный алфавит, это не будет иметь никакого значения". Что является правдой.
Томас Климпел
1
журналN[N]
1
@JoshuaGrochow Это именно то, что я имел в виду, это не будет иметь никакого значения ". Это правда. Сейчас я попытался ответить на ваш комментарий" Изоморфизм строк / цветовой изоморфизм не попадает в этот класс ". Мне понравилось изучать некоторые уроки из Андреас Бласс и Юрий Гуревич на пути, которые также пытаются сосредоточиться на концептуальных моментах. Я рад, что Бабай исправил свой алгоритм сейчас, так что я не чувствую обязательства (или давления), чтобы исследовать, являются ли изоморфизм графов и изоморфизм строк полиномиальным эквивалентом времени (В этом контексте я написал этот ответ.)
Томас Климпел
Я смущен, почему вы сравниваете прогресс по GI с результатами дерандомизации.
Сашо Николов