2014 dxdy logo

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

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





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


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

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


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

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

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

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

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

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



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

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


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

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