Граф Изоморфизм и скрытые подгруппы

23

Я пытаюсь понять связь между изоморфизмом графов и проблемой скрытой подгруппы. Есть хорошая ссылка для этого?

Суреш Венкат
источник
2
Tssk, не только нам нужно вылечить вашу болезнь желудочно-кишечного тракта, но и всех бедных читателей вашего вопроса, которые также заразились! (Это в шутку, я тоже несколько склонен к болезни желудочно-кишечного тракта.)
Андрас Саламон
1
слишком верно. Теперь я должен держаться подальше от Дейва Бэкона :)
Суреш Венкат
2
К вашему сведению, следующая относительно недавняя статья, я думаю, положила в гроб гвоздь на «алгоритмы квантового сита» для GI, который охватывает многие попытки до сих пор (и не упоминается в блоге Дейва Бэкона): dx.doi.org/ 10.1137 / 080724101 . В статье много говорится о теории представлений, но вводной части нет, и она довольно хорошо читается.
Джошуа Грохов

Ответы:

20

Ссылки можно найти в ответе martinschwarz, но вот краткое изложение нескольких сокращений.

Симметрическая группа действует на графах из n вершин, переставляя вершины. Определение того, являются ли два графа изоморфными, эквивалентно полиномиальному времени для вычисления порождающего множества полиномиального размера для . A u t ( G )SnAut(G)

Сведение к HSP над симметричной группой (где - количество переменных в графе). Функция является , где есть перестановка в и является перестановка версии . Тогда постоянна на смежных классах и различна на разных смежных классах (заметим, что образ состоит из всех графов, изоморфных ). Поскольку скрытой подгруппой является именно , если бы мы могли решить этот HSP, то у нас был бы генераторный набор для n f f ( p ) = p ( G ) p S n p ( G ) G f A u t ( G ) f G A u t ( G ) A u t ( G )Snnff(p)=p(G)pSnp(G)GfAut(G)fGAut(G)Aut(G), это все, что нам нужно для решения GI (см. выше).

Сведение к HSP по . Если мы хотим знать , изоморфны ли два графа и на вершинах, рассмотрим граф который является несвязным объединением и на вершинах. Пусть действует на вершины, меняя местами на для . Либо либо . Как и раньше, пусть где G Н н К О Н 2 н Z / 2 Z я п + я я = 1 , . , , , n A u t ( K ) = A u t ( G ) × A u t ( H ) A u t ( K ) = ( ASnZ/2ZGHnKGH2nZ/2Zin+ii=1,...,nAut(K)=Aut(G)×Aut(H) F ( х ) = х ( К ) х S пZ / 2 Z К е U т ( K ) A u t ( K ) G H KAut(K)=(Aut(G)×Aut(H))semidirectZ/2Zf(x)=x(K)xтеперь является элементом который действует на как описано. Скрытая подгруппа, ассоциированная с является в точности , как в предыдущем сокращении. Если мы решим этот HSP, мы получим генераторную установку для . Тогда легко проверить, содержит ли порождающий набор какой-либо элемент, который заменяет копию на копию внутри (имеет нетривиальный компонент ).SnZ/2ZKfAut(K)Aut(K)GHKZ/2Z

Джошуа Грохов
источник
17

Возможно, вы захотите прочитать недавнее сообщение в блоге Дэйва Бэкона « Изоморфизм графов» со ссылками на литературу.

Мартин Шварц
источник
14

«Квантовые алгоритмы для алгебраических задач» Эндрю Чайлдса и Вима ван Дама arXiv: 0812.0380 - очень хорошая обзорная статья, которая содержит хорошее введение в неабелеву HSP и его связь с изоморфизмом графов.

dabacon
источник