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

23

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

cc.complexity-theory reference-request quantum-computing graph-isomorphism Суреш Венкат
источник

2

Tssk, не только нам нужно вылечить вашу болезнь желудочно-кишечного тракта, но и всех бедных читателей вашего вопроса, которые также заразились! (Это в шутку, я тоже несколько склонен к болезни желудочно-кишечного тракта.)

Андрас Саламон

1

слишком верно. Теперь я должен держаться подальше от Дейва Бэкона :)

Суреш Венкат

2

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

Джошуа Грохов

20

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

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

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

Сведение к HSP по . Если мы хотим знать , изоморфны ли два графа и на вершинах, рассмотрим граф который является несвязным объединением и на вершинах. Пусть действует на вершины, меняя местами на для . Либо либо . Как и раньше, пусть где $S_n \wr \mathbb{Z}/2\mathbb{Z}$ $G$ $H$ $n$ $K$ $G$ $H$ $2n$ $\mathbb{Z}/2\mathbb{Z}$ $i$ $n+i$ $i=1,...,n$ $Aut(K) = Aut(G) \times Aut(H)$ $Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$ $f(x)=x(K)$ $x$ теперь является элементом который действует на как описано. Скрытая подгруппа, ассоциированная с является в точности , как в предыдущем сокращении. Если мы решим этот HSP, мы получим генераторную установку для . Тогда легко проверить, содержит ли порождающий набор какой-либо элемент, который заменяет копию на копию внутри (имеет нетривиальный компонент ). $S_n \wr \mathbb{Z}/2\mathbb{Z}$ $K$ $f$ $Aut(K)$ $Aut(K)$ $G$ $H$ $K$ $\mathbb{Z}/2\mathbb{Z}$

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

17

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

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

14

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

dabacon
источник

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

Ответы: