Новость: задача GI имеет квазиполиномиальную сложность?

[bin]

Один из наиболее известных специалистов по проблеме изоморфизма графов László Babai утверждает, что задача изоморфизма графов решается в наихудшем случае за квазиполиномиальное время от числа вершин графа. 10 ноября 2015 он выступит с докладом "Graph Isomorphism in Quasipolynomial Time" на семинаре в Чикагском университете. Если у кого из форумчан будет возможность там оказаться - поделитесь, пожалуйста, своими впечатлениями в этой теме. Пока, конечно, это еще непризнаный результат, но в любом случае к этому событию стоит отнестись серьезно.

[maxal]

Вот еще кое-какие детали: http://www.scottaaronson.com/blog/?p=2521

[maxal]

Подробности: http://jeremykun.com/2015/11/12/a-quasi ... e-details/

[bin]

Появилась видеозапись доклада:
http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4

Докладчик отметил, что к проблеме изоморфизма графов есть 2 подхода: комбинаторный и теоретико-групповой. Я пытаюсь развивать комбинаторный и не считаю себя знатоком теоретико-группового, хотя знаком с упомянутыми в докладе работами (Luks, McKay). Было бы очень полезно, если бы знатоки теории групп высказались здесь по этому докладу.

У меня недоумение вызвало заявление, что "изоморфизм графов сводится к изоморфизму строк". Пусть даны строки "абггв" и "гагвб", то, что они перестановочно равны (изоморфны?), доказывается за полиномиальное время, т.к. сортировка каждой из них в алфавитном порядке дает одну и ту же строку "абвгг".

[arseniiv]

Сортировку нельзя, ибо не обязательно допустимы любые перестановки символов. В общем случае дана какая-то подгруппа перестановок индексов.

-- Вс ноя 22, 2015 03:34:18 --

И это видно по последней ссылке maxal в разделе The Main Result.

[bin]

arseniiv в сообщении #1075582 писал(а):

Сортировку нельзя, ибо не обязательно допустимы любые перестановки символов.

А можно дать точную формулировку задачи изоморфизма строк? (Т.е. в графах допустима любая перенумерация вершин, нпр., в графе с пятью вершинами любая вершина может иметь номер от 1 до 5, а в строке из пяти символов не всякий символ может иметь номер от 1 до 5?)

[arseniiv]

автор упоминаемого обзора писал(а):

Now given a set $X$ and a group $G$ acting on $X$, there is a natural action of $G$ on strings over $X$, denoted $x^\sigma$, by permuting the indices $x^{\sigma}(i) = x(\sigma(i))$. So you can ask the natural question: given two strings $x,y$ and a representation of a group $G$ acting on $X$ by a set of generating permutations of $G$, is there a $\sigma \in G$ with $x^\sigma = y$? This problem is called the string isomorphism problem, and it’s clearly in NP.

Now if you call $\textup{ISO}_G(x,y)$ the set of all permutations in $G$ that map $x$ to $y$, and you call $\textup{Aut}_G(x) = \textup{ISO}_G(x,x)$, then the actual theorem Babai claims to have proved is the following.

Theorem: Given a generating set for a group $G$ of permutations of a set $X$ and a string $x$, there is a quasipolynomial time algorithm which produces a generating set of the subgroup $\textup{Aut}_G(x)$ of $G$, i.e. the string automorphisms of $x$ that lie in in $G$.

Связь этого и GI я копировать оттуда не буду.

-- Вс ноя 22, 2015 03:48:48 --

bin в сообщении #1075583 писал(а):

а в строке из пяти символов не всякий символ может иметь номер от 1 до 5?

Не понял, как это можно получить из того, что я написал.

[bin]

Спасибо, я это читал. А вот как понять Ваше "не обязательно допустимы любые перестановки символов". Нпр, перестановки символа 1 допустимы с символами 2 и 4, с остальными не допустимы, символ 1 равен символу 2 и для символа 2 допустимы перестановки с символом 1 и 4, а вот символ 3 равен символу 1, но для него не допустима перестановка с символом 2. Алфавит не ограничен, заменяем символы 1 и 2 на новый символ $s_1$, а символ 3 на $s_2$, и т.д. В итоге получим строку, которую можно сортировать с учетом ограничений на перестановки.

-- Вс ноя 22, 2015 02:10:27 --

BTW В приведенном отрывке из конспекта в большой степени отразилось понимание автора конспекта, а в докладе на доске была нарисована одна строка, что-то вроде ABBCDF и вторая BAB, дальше докладчик поставил многоточие "..." и сказал что-то вроде "далее понятно", и ни про какие ограничения на перестановки я тут не услышал.

-- Вс ноя 22, 2015 02:19:50 --

PS Я вижу, что в моем примере с заменой символов может возникнуть проблема однозначной замены в двух строках, но ИМХО объяснять такие детали следует докладчику, а не слушателям.

-- Вс ноя 22, 2015 02:22:44 --

arseniiv в сообщении #1075585 писал(а):

Не понял, как это можно получить из того, что я написал.

См.:

arseniiv в сообщении #1075582 писал(а):

Сортировку нельзя

[arseniiv]

bin в сообщении #1075586 писал(а):

Нпр, перестановки символа 1 допустимы с символами 2 и 4, с остальными не допустимы, символ 1 равен символу 2 и для символа 2 допустимы перестановки с символом 1 и 4, а вот символ 3 равен символу 1, но для него не допустима перестановка с символом 2. Алфавит не ограничен, заменяем символы 1 и 2 на новый символ $s_1$, а символ 3 на $s_2$, и т.д. В итоге получим строку, которую можно сортировать с учетом ограничений на перестановки.

Если перестановка $(124)$ входит в группу, а $(12)$ — нет, что предложите?

-- Вс ноя 22, 2015 05:52:25 --

(Оффтоп)

bin в сообщении #1075586 писал(а):

arseniiv в сообщении #1075585 писал(а):

Не понял, как это можно получить из того, что я написал.

См.:

arseniiv в сообщении #1075582 писал(а):

Сортировку нельзя

Ясно. Вынужден признать, что тогда не понимаю, что вообще имелось в виду под

bin в сообщении #1075583 писал(а):

а в строке из пяти символов не всякий символ может иметь номер от 1 до 5?

При очевидном на первый взгляд понимании этот вопрос имеет ответ «нет», т. к. для каждого индекса $i\in I$ в строке $s\colon I\to A$ есть символ $s(i)$ с данным индексом. Если не это имелось в виду, то, если можно, поясните, что. Если это, то непонятно, какое противоречие это должно иметь с предыдущей частью высказывания:

bin в сообщении #1075583 писал(а):

Т.е. в графах допустима любая перенумерация вершин, нпр., в графе с пятью вершинами любая вершина может иметь номер от 1 до 5

[bin]

arseniiv,
еще раз: в графе любой вершине могу присвоить номер первой, любой из оставшихся - нУмер второй и т.д. В строке я могу любой символ передвинуть на первую, вторую и т.д. позиции? Если могу, то сортировка строк (т.е. символов в строке) допустима при тестировании "изоморфизма" строк, а если нет, то определение изоморфизма строк нуждается в существенном уточнении.

[arseniiv]

bin в сообщении #1077538 писал(а):

В строке я могу любой символ передвинуть на первую, вторую и т.д. позиции?

Зависит от $G$.

-- Сб ноя 28, 2015 08:29:59 --

А именно, если $G = S_n$, где $n$ — длина строки, то да, а во всех остальных случаях — нет.

[g______d]

http://arxiv.org/abs/1512.03547

[maxal]

Пояснение про графы Джонсона:
http://mathoverflow.net/questions/22760 ... -important

[bin]

Интересно, здесь, как и во всей сетке: никто сабж не обсуждает, т.е. не опровергает и не подтверждает, а только упоминает. Такой ситуации ИМХО м.б. 3 объяснения:

1) Всем всё настолько понятно, что никто не видит необходимости говорить об очевидном.
2) Всем всё настолько не понятно, что никто ничего по существу сказать не может.
3) Все, как и я, считают свои познания в теории групп недостаточными и ждут, когда более сведущие коллеги им доступно объяснят.

Но сколько можно ждать? Я пытаюсь понять статью с архива. Дошел до стр. 11, где прочел:

Цитата:

For a function $f$ we usually write $x^{f}$ for $f(x)$.

В связи с этим вопрос: автор, конечно, имеет право обозначать, как он хочет, но зачем вводить столь неудобные обозначения? Через страницу мы встречаем, нпр.:

Цитата:

Johnson groups $\mathfrak{G_{\mathrm{k}}^{(t)}}$

и до того (p.1):

Цитата:

$f(n)\leq\exp(C(\log n)^{c})$

видимо, я уже сумел запутаться в обозначениях?

[grizzly]

bin в сообщении #1110652 писал(а):

В связи с этим вопрос: автор, конечно, имеет право обозначать, как он хочет, но зачем вводить столь неудобные обозначения?

В данном случае использовано одно из стандартных обозначений (так называемая postfix notation -- можете поискать об этом). Я же могу только упомянуть один любопытный пример использования -- факториал.