2014 dxdy logo

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

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





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


27/04/09
18493
Уфа
$\Psi$ и $\Omega$, насколько понимаю, свободные в том месте. $\mathfrak S(A)$ — группа перестановок элементов $A$.

-- Вт апр 05, 2016 03:49:23 --

(Там именно $\mathfrak S$, как написали вы, и не $\mathfrak G$, как написано у bin.)

Ещё забыто
вторая версия статьи писал(а):
Definition 2.4.8. Let $\mathfrak X = (\Omega;\mathcal R)$ be a relational structure. We say that $x,y \in\Omega$ are strong twins for $\mathfrak X$ if they are strong twins for $\operatorname{Aut}(\mathfrak X)$. We analogously transfer all concepts introduced in this section from groups to structures via their automorphism groups (weak twins, strongly/weakly symmetrical sets, symmetry defect). For instance, the (relative) symmetry defect of $\mathfrak X$ is the (relative) symmetry defect of $\operatorname{Aut}(\mathfrak X)$.
т. к. (двудольный) граф явно понимается как relational structure (пока не дочитал до Observation 7.2.2, но тут и гадать не следует).

[В цитате выше я где-то, видимо, забыл проставить курсив. Уже закрыл статью.]

-- Вт апр 05, 2016 04:03:31 --

Далее (это пересказ 7.2 с начала), в двудольных графах $(V_1,V_2,E)$ доли маркированы (первая и вторая), и изоморфизмы (стало быть, и автоморфизмы) не отображают вершины первой доли одного графа в вершины второй, и наоборот. При рассмотрении colored двудольных графов $(V_1,V_2,E,f)$, где $f\colon V_1\cup V_2\to\mathrm{colors}$, $f(V_1)\cap f(V_2)=\varnothing$; изоморфизмы, конечно, сохраняют цвета.

Ещё:
вторая версия статьи писал(а):
Definition 7.2.1. Let $X = (V_1,V_2;E,f)$ be a colored bipartite graph. We say that vertices $x,y \in V_i, x \ne y$ are twins if they have the same color (in particular, they belong to the same part) and they have the same neighborhood: $N(x) = N(y)$. For a subset $T \subseteq V_i$ we use the phrase “all vertices in $T$ are twins” to mean that all pairs of distinct vertices in $T$ are twins.
чего как раз не хватало, потому что в Observation 7.2.2 три пункта.

Про окрестность искать не буду, моей помощи bin уже достаточно. :mrgreen:

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


22/09/09
1899
arseniiv в сообщении #1112215 писал(а):
Про окрестность искать не буду, моей помощи bin уже достаточно.
Я не про это спрашивал. Меня удивило доказательство из одного слова "очевидно".

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


27/04/09
18493
Уфа
bin в сообщении #1112473 писал(а):
Я не про это спрашивал.
А я и не про то, про что вы спрашивали. :roll: Я про
g______d в сообщении #1112213 писал(а):
Это не полностью
потому что и правда было не полностью. Ваших цитат было недостаточно для понимания Observation 7.2.2.

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


28/01/14
20
Уже нет.
Ласло Бабай пересмотрел свой результат. Теперь утверждается, что задача об изоморфизме графов имеет субэкспоненциальную сложность.

Об этом буквально вчера написал сам Бабай:

http://people.cs.uchicago.edu/~laci/update.html

Если я правильно понимаю, задача остаётся в "серой зоне".

 Профиль  
                  
 
 Re: Новость: задача GI имеет квазиполиномиальную сложность?
Сообщение24.01.2017, 15:35 


13/11/15
3
Dave Karapetian
Ошибка уже исправлена, информация по Вашей же ссылке.
Нашедший ошибку Хельфготт в своем блоге корректность исправления признал

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


28/01/14
20
a1981 в сообщении #1187084 писал(а):
Dave Karapetian
Ошибка уже исправлена, информация по Вашей же ссылке.
Нашедший ошибку Хельфготт в своем блоге корректность исправления признал



Спасибо большое.

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

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



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

Сейчас этот форум просматривают: Google Adsense [Bot]


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

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