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

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

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

Какие еще доказательства мы должны верить, что $GI$ не в $P$ ?

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

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

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

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

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

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

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

Количество битов, необходимых для хранения немаркированного графа, равно из . Смотри Наор, Мони. «Краткое представление общих немеченых графов». Дискретная прикладная математика 28,3 (1990): 303-307. Доказательство метода сжатия немного чище, если я помню. Во всяком случае, позволяет вызов, набор . Пусть для помеченных графов.$log_{2}$UL=2 (${n\choose 2}-n log(n) +O(n)$$U$$L=2^{{n\choose 2}}$

--Haskell notation
graphCanonicalForm :: L -> U

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

Б о о л л $U^L$ и если вы конвертируете в экспоненту. Простое изучение сигнатур типов, перевод графов в каноническую форму выглядит проще, но, как показано выше, GC облегчает GI.$Bool^{L^{L}}$

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

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

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

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

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

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

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

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

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

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