Проблема изоморфизма графов (GI), возможно, является наиболее известным кандидатом в NP-промежуточную задачу. Самый известный алгоритм - это субэкспоненциальный алгоритм с временем выполнения . Известно, что GI не является -полным, если не разрушится полиномиальная иерархия .NP
Каковы будут теоретические последствия сложности алгоритма квазиполиномиального времени для задачи об изоморфизме графа?
Будет ли квазиполиномиальный алгоритм времени для GI опровергать какие-либо известные гипотезы в теории сложности?
Другие аналогичные проблемы, такие как минимальное доминирующее множество в задаче о турнирах, проблема изоморфизма групп и проблема изоморфизма турниров, имеют алгоритмы квазиполиномиального времени ( QP ). Последние две проблемы сводятся за полиномиальное время к GI.
Можем ли мы эффективно уменьшить проблему минимального доминирующего множества в турнирах до GI?
Есть ли какие-либо предположения о том, что GI трудно для QP?
Обновление (2015-12-14) : Бабаи опубликовал предварительный черновик статьи по arXiv для своего алгоритма квазиполиномиального времени для GI.
Обновление (2017-01-04) : Бабай отказался от утверждения, что алгоритм находится в квазиполиномиальном времени, согласно новому анализу, алгоритм находится в субэкспоненциальном времени который находится внутри .2 n o ( 1 )
Обновление (2017-01-09) : Бабаи восстановил квазиполиномиальное требование о времени, заменив нарушающую процедуру более эффективной.
источник
Ответы:
Насколько я могу судить, если вы просто спросите о последствиях самого факта (в виде черного ящика), что GI находится в QP, я думаю, что ответ будет очень небольшим. Единственное, о чем я могу думать, это не теорема, а следствие для направлений исследований, это групповой изоморфизм. Поскольку GroupIso сводится к GI, и мы даже не знаем, находится ли GroupIso в P, размещение GroupIso в P можно рассматривать как важное препятствие для помещения GI в P (если вы думаете, что последнее может иметь место).
Однако, поскольку тривиальным алгоритмом для GroupIso является , тогда, когда сложность GI была на уровне 2 ˜ O ( √Nжурналn + O ( 1 ) , нам пришлось пройти долгий путь в улучшении сложности GI, прежде чем GroupIso сталнепосредственным существеннымпрепятствием для введения GI в P. Но если GI находится в QP, то GroupIso становится гораздо более значимым препятствием для дальнейшего улучшения GI. (Конечно, показатель степени в квазиполиноме все еще является потенциально значимым разрывом, но разрыв становитсянамногоменьше, когда GI находится в QP.)2О~( н√)
источник
Относительно последнего вопроса: теорема иерархии времени сразу подразумевает, что QP не имеет полных проблем при многочленном или многочленовом редукциях за полиномиальное время. (С другой стороны, каждая задача, кроме save и Σ ∗ , QP-трудна при квазиполиномиальных редукциях.) Таким образом, предполагая, что результат Бабая верен, GI не QP-сложен.∅ Σ*
источник
Более или менее похожи на последствия алгоритма детерминированного полиномиального времени для тестирования простоты, алгоритма детерминированного полиномиального времени для линейного программирования и другого случая, когда были известны практически эффективные (рандомизированные) алгоритмы (с редкими патологическими примерами, когда алгоритм стал неэффективным) и используется в течение длительного времени. Это подтверждает гипотезу о том, что практическая эффективность является хорошим показателем существования детерминированных теоретических алгоритмов, преодолевающих проблемы редких патологических примеров.
Нет, предположения скорее идут в противоположную сторону, а именно, что GI находится в P. Так как GI находится в NP, будет невозможно опровергнуть этот тип предположения в ближайшее время.
Минимальное доминирующее множество не является проблемой изоморфизма, поэтому нет никаких причин, по которым его следует приводить к GI.
Мы даже не знаем, как свести проблему изоморфизма строк к GI, и это, по крайней мере, проблема изоморфизма. Доказательство Бабая показало, что в QP был изоморфизм струн, так что ... А что для QP трудно даже предполагать? Тяжело при полиномиальном сокращении времени?
Из введения Франсуа Ле Галля и Дэвида Дж. Розенбаума "О проблемах группового и изоморфизма цвета"
Изменить: Этот ответ был дан в контексте отказа от результата Бабая, прежде чем он объявил исправление. Это говорит о том, что небольшое обобщение проблемы изоморфизма графов, предложенной проблемой изоморфизма струн, является действительно важной проблемой. Здесь подразумевается, что любой разумный алгоритм для задачи об изоморфизме графа приведет к аналогичному алгоритму для обобщенной задачи об изоморфизме графа. Обобщенная задача полиномиально время эквивалентна задача множества стабилизатора , то проблема пересечения группы , задача смежного класса пересечения, то проблема набора Транспортера ... Идея этого ожидания в том , что обобщенная проблема будет возникать в рекурсивной частилюбого разумного алгоритма, поэтому он должен быть решен в любом случае. (И вполне возможно, что обобщенная задача за полиномиальное время эквивалентна изоморфизму графа.)
Теперь комментарии Джошуа Грохоу показывают, что мне не удалось объяснить концептуальную важность недостающих фрагментов из проблемы изоморфизма строк. Для бесконечных структур может быть легче понять, что действительный изоморфизм должен не только сохранять данную структуру, но также принадлежать к соответствующей категории функций (например, категории непрерывных функций). Для конечных структур аналогичное явление в основном имеет место для фактор-структур, где соответствующая категория функций должна быть совместима с данными коэффициентами. Материал Джонсона является типичным примером таких отношений, например, логика разбиения работает над двумя подмножествами элементов некоторого базового набора. Также обратите внимание, что ограничение допустимой категории для изоморфизмов часто облегчает задачу проверки изоморфизма,
Проблема с обобщениями проблемы изоморфизма графа состоит в том, где остановиться. Почему бы не обобщить настолько, чтобы охватить проблему изоморфизма групп перестановок? Этот вопрос действительно сложен, так как многие нетривиальные результаты для изоморфизма графов, вероятно, перенесут и на изоморфизм групп перестановок. Но здесь представляется более разумным рассматривать теорию групп вычислительных перестановок как отдельный предмет, даже если она действительно имеет тесную связь с проблемой изоморфизма графов.
источник