Каковы доказательства того, что изоморфизм графов отсутствует в

23

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

Одним из таких доказательств является Nп -полнота ограниченной задачи автоморфизма графа (задача об автоморфизме свободного фиксированного графа является Nп -полной). Эта проблема и другие обобщения гя были изучены в « Некоторые NP-полные задачи, подобные изоморфизму графа » Люби. Некоторые могут возразить , как доказательство того факта , что , несмотря на более чем 45 лет ни один не найден полиномиальный алгоритм для гя .

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

Мухаммед Аль-Туркистани
источник
2
Подграф-изоморфизм также NP-полон.
1
Несколько слабым доказательством является растущий класс проблем, эквивалентных логическому пространству для GI, но ни одна из которых, кажется, не имеет очевидных алгоритмов разветвления. (Конечно, если у одного из них есть алгоритм polytime, то у всех так и есть.)
Андрас Саламон,
косвенные доказательства, аналогичные P против NP: десятилетия оптимизации алгоритмов GI, например, nauty, которые все еще имеют экспериментально проверяемые не-P тенденции наихудшего случая, по-видимому, главным образом на случайных регулярных графах.
vzn
Что Вы думаете об этом? dharwadker.org/tevet/isomorphism
Анна Томскова

Ответы:

11

До этого вопроса я считал, что изоморфизм графов может быть в P, т. Е. Нет никаких доказательств того, что GI не в P. Поэтому я спросил себя, что будет считать доказательством для меня: если бы существовали зрелые алгоритмы для - групповой изоморфизм, который полностью использовал доступную структуру p -групп и все еще не имел бы надежды на достижение полиномиального времени выполнения, тогда я согласился бы, что GI, вероятно, отсутствует в P. Существуют известные алгоритмы, которые используют доступную структуру, например тестирование изоморфизма для p - групп. О'Брайен (1994)ппп, но я не прочитал его достаточно подробно, чтобы судить, полностью ли он использует имеющуюся структуру или есть ли надежда улучшить этот алгоритм (без использования дополнительной неочевидной структуры -групп) для достижения полиномиального времени выполнения.п

Но я знал, что Дик Липтон призвал к действию в конце 2011 года, чтобы прояснить вычислительную сложность проблемы изоморфизма группы в целом и проблемы изоморфизма группы в частности. Так что я погуглилп

site:https://rjlipton.wordpress.com group isomorphism

чтобы увидеть, был ли призыв к действию успешным. Это было действительно:

  1. Проблема группового изоморфизма: возможная проблема с многочленом?
  2. Достижения в групповом изоморфизме
  3. Три из КХЦ: прогресс в групповом изоморфизме

В последнем посте рассматривается статья, в которой достигается для некоторых важных семейств групп, используется большая часть доступной структуры, и признается вышеупомянутая статья 1994 года. Поскольку n O ( log log n ) ограничено временем выполнения и совместимо с опытом, что изоморфизм графов не сложен на практике, и с опытом, что никто не может придумать алгоритм полиномиального времени (даже для группового изоморфизма), это можно считать доказательством того, что GI не находится в P ,NО(журналжурналN)NО(журналжурналN)

Томас Климпел
источник
rjlipton.wordpress.com/2015/03/05/news-on-intermediate-problems также был найден в результате моего поиска. Это приводит теорема 2 Изоморфизм графов в . Кроме того, каждая проблема обещания в S Z K принадлежит B P P M C S P, как определено для задач обещания. рпMСSпSZКВппMСSпЭто доказательство того, что GI не является NP-завершенным, но это не был вопрос здесь. Позвольте мне добавить, что я не вижу проблем с длиной или стилем моего ответа, потому что я интерпретирую запрос о предоставлении доказательств как запрос о мотивированном мнении.
Томас Климпел
5
Я не слежу за твоими рассуждениями. Как вы можете знать, что «доступная структура» «полностью эксплуатируется»? Если что-нибудь, разве статья Грохова-Цяо не предполагает, что с классами когомологий можно сделать гораздо больше?
Сашо Николов
@SashoNikolov Под «доступной структурой» я имею в виду знания о структуре в сообществе теории групп, связанных сообществах и существующих публикациях. Примерами того, что структура не «полностью используется», являются публикации, основная цель которых состоит в том, чтобы придумать практичный реализуемый алгоритм, который поэтому останавливается в некоторой точке и просто упоминает остальные ограничения без четких указаний, являются ли они фундаментальными. В работе Грохова-Цяо были рассмотрены те, которые непосредственно атаковали вычислительную сложность группового изоморфизма, и, следовательно, ее результаты являются хорошим доказательством.
Томас Климпел
11

Наименьший набор перестановок, который вы должны проверить, чтобы убедиться, что в настройках черного ящика нет нетривиальных перестановок, лучше, чем но все еще экспоненциальный, OEIS A186202 .N!

Количество битов, необходимых для хранения немаркированного графа, равно из . Смотри Наор, Мони. «Краткое представление общих немеченых графов». Дискретная прикладная математика 28,3 (1990): 303-307. Доказательство метода сжатия немного чище, если я помню. Во всяком случае, позволяет вызов, набор . Пусть для помеченных графов.Lог2UL=2 ( n(N2)-NLог(N)+О(N)ULзнак равно2(N2)

--Haskell notation
graphCanonicalForm :: L -> U

graphIsomorphism :: L -> L -> Bool
graphIsomorphism a b = (graphCanonicalForm a) == (graphCanonicalForm b)    

Б о о л л лUL и если вы конвертируете в экспоненту. Простое изучение сигнатур типов, перевод графов в каноническую форму выглядит проще, но, как показано выше, GC облегчает GI.ВооLLL

Чад Brewbaker
источник
Спасибо. Насколько сильны такие аргументы?
Мухаммед Аль-Туркистани
есть ли ссылка, которая документирует эту связь дальше?
vzn
3
@ MohammadAl-Turkistany: Это в основном аргумент сложности запроса. Но известные алгоритмы, например, Babai-Luks 1983, уже преодолели эту границу, я думаю, с существенным отрывом (что-то вроде против 2 2N ). 2N
Джошуа Грохов
1
@ChadBrewbaker: Если ваша проблема закодирована, и сложность среднего случая, я уверен, что nauty работает значительно лучше, чем ваш алгоритм. (Обратите внимание , что наиболее известным нижняя граница nauty является (Miyazaki , 1996), а также алгоритм поли-времени было найдено для графиков Миязаки. Простой анализ показывает , нижняя граница ( 3 / 2 ) п по вашему алгоритму.) Кроме того, GI в среднем случае линейного времени (Бабаи-Кучера). Ω(2N/20)(3/2)N
Джошуа Грохов
2
@ MohammadAl-Turkistany: этот вопрос заставил меня глубже задуматься о моих убеждениях в сложности GI. По поводу вашего другого вопроса, обратите внимание, что если не будет многократного сокращения Тьюринга (или даже много-одного) с GI до GA, то P NP.
Джошуа Грохов
8

Кодзэно в своей статье Проблемы клики эквивалентно изоморфизм графов , дает доказательство того, что не является в Р . Следующее из бумаги:гяP

«Тем не менее, вполне вероятно, что найти алгоритм полиномиального времени для изоморфизма графа будет так же сложно, как найти алгоритм полиномиального времени для NP-полной задачи. В поддержку этого утверждения мы даем задачу, эквивалентную изоморфизму графа, - небольшое возмущение из которых NP-полный. "

Также Бабай в своей недавней прорывной работе « Изоморфизм графов в квазиполиномиальное время» приводит аргумент против существования эффективных алгоритмов для GI. Он отмечает , что проблема группового изоморфизма (который сводится к Г) , является основным препятствием для размещения GI в . Проблема группы Изоморфизм (группы определяются их Кэли tableis) разрешима в п O ( журнал N ) , и не известно , чтобы быть в P .PnO(logn)P

Вот выдержка из статьи Бабая:

Результат настоящей статьи усиливает значимость проблемы группового изоморфизма (и заявленной проблемы вызова) как барьера для помещения GI в P. Вполне возможно, что промежуточный статус GI (ни NP-полный, ни полиномиальное время) будет сохраняться.

Мухаммед Аль-Туркистани
источник
2
Из лема Козена. 3 можно получить более простой пример этого явления: а именно, индуцированный изоморфизм подграфа (является ли индуцированным подграфом в G ) является точно GI, когда | G | = | H | , но NP-сложный, когда | G | = с | H | для любого с > 1ЧАСг|г|знак равно|ЧАС||г|знак равнос|ЧАС|с>1, Для дискретных параметров мы знаем, что в P есть проблемы, которые быстро становятся NP-полными (например, 2SAT против 3SAT). Знаете ли вы, есть ли примеры проблем в P с некоторым непрерывным параметром, которые становятся NP-полными при резком пороге? Если это так, то такого рода рассуждения не будут большим доказательством того, что Г.И. отсутствует в P, но я не могу придумать такой пример с головы до головы.
Джошуа Грохов
2
@ JoshuaGrochow Нет, я не знаю ни о каких проблемах с таким решением. Но для задач оптимизации я знаю , что найти задание , удовлетворяющее из пунктов находится в P , находя задание , удовлетворяющее из пунктов является -трудной даже для выполнимых 3SAT формул ( ). 7/8п N P ε > 07/8+εNпε>0
Мохаммад Аль-Туркистани
К сожалению, ответ Климпеля уже содержит доказательства изоморфизма группы. В любом случае, полезно иметь точку зрения Бабая на этот счет.
Мохаммед Аль-Туркистани
5

вот другие результаты, которые еще не цитировались

  • О твердости изоморфизма графов / Torán FOCS 2000 и SIAM J. Comput. 33, 5 1093-1108.

    Мы показываем, что проблема изоморфизма графов трудна при равномерном DLOGTIME редукции AC 0 many-one для классов сложности NL, PL (вероятностного логарифмического пространства) для каждого модульного класса логарифмического пространства Mod k L и для класса DET задач NC 1, сводимых к определитель. Это самые сильные из известных результатов твердости для задачи об изоморфизме графов, и они предполагают редуцированное рандомизированное логарифмическое пространство от задачи идеального соответствия к изоморфизму графов. Мы также исследуем результаты твердости для задачи автоморфизма графа.

  • Изоморфизм графов не сводим AC 0 к изоморфизму групп / Chattopadhyay, Toran, Wagner

    Мы даем новую верхнюю границу для задач изоморфизма групп и квазигрупп, когда входные структуры заданы явно таблицами умножения. Мы показываем, что эти проблемы могут быть вычислены с помощью недетерминированных цепей полиномиального размера неограниченного разветвления с O (log log n) глубиной и O (log 2 n) недетерминированных битов, где n - количество элементов группы. Это улучшает существующую верхнюю границу из [Wol94] для задач. В предыдущей верхней границе схемы имеют ограниченный веер, но глубину O (log 2 n), а также O (log 2 n) недетерминированных битов. Затем мы докажем, что вид схем из нашей верхней границы не может вычислить функцию четности. Так как паритет AC 0приводимый к изоморфизму графа, это означает, что изоморфизм графа строго сложнее, чем изоморфизм группы или квазигруппы в порядке, определяемом редукциями AC 0 .

ВЗН
источник
4
AС0
о «сильнейших известных нижних оценках GI», ofc GI в NP, поэтому фактическое доказательство того, что GI не находится в P, эквивалентно P ≠ NP! (возможно через NPI ≠ ∅) ...
vzn
4
Да, но, например, было бы неплохо знать, что G-P-hard! (Конечно, P-твердость очень мало связана с тем, чтобы показать, что что-то не в P, но это, по крайней мере, говорит о том, что GI не в NC!)
Джошуа Грохов