2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение05.11.2015, 01:53 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение06.11.2015, 23:18 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение13.11.2015, 04:56 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение22.11.2015, 01:09 
Аватара пользователя


22/09/09

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

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

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

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение22.11.2015, 01:32 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение22.11.2015, 01:40 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение22.11.2015, 01:47 
Заслуженный участник


27/04/09
28128
автор упоминаемого обзора писал(а):
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?
Не понял, как это можно получить из того, что я написал.

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение22.11.2015, 01:59 
Аватара пользователя


22/09/09

1907
Спасибо, я это читал. А вот как понять Ваше "не обязательно допустимы любые перестановки символов". Нпр, перестановки символа 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 писал(а):
Сортировку нельзя

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение22.11.2015, 03:38 
Заслуженный участник


27/04/09
28128
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

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение28.11.2015, 02:01 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение28.11.2015, 06:27 
Заслуженный участник


27/04/09
28128
bin в сообщении #1077538 писал(а):
В строке я могу любой символ передвинуть на первую, вторую и т.д. позиции?
Зависит от $G$.

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

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

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение14.12.2015, 08:47 
Заслуженный участник
Аватара пользователя


08/11/11
5940
http://arxiv.org/abs/1512.03547

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение06.01.2016, 14:48 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение30.03.2016, 23:51 
Аватара пользователя


22/09/09

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

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

Но сколько можно ждать? Я пытаюсь понять статью с архива. Дошел до стр. 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})$
видимо, я уже сумел запутаться в обозначениях? :-(

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение31.03.2016, 00:19 
Заслуженный участник
Аватара пользователя


09/09/14
6328
bin в сообщении #1110652 писал(а):
В связи с этим вопрос: автор, конечно, имеет право обозначать, как он хочет, но зачем вводить столь неудобные обозначения?
В данном случае использовано одно из стандартных обозначений (так называемая postfix notation -- можете поискать об этом). Я же могу только упомянуть один любопытный пример использования -- факториал.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу 1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group