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

[arseniiv]

$\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 уже достаточно.

[bin]

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

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

Я не про это спрашивал. Меня удивило доказательство из одного слова "очевидно".

[arseniiv]

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

Я не про это спрашивал.

А я и не про то, про что вы спрашивали. Я про

g______d в сообщении #1112213 писал(а):

Это не полностью

потому что и правда было не полностью. Ваших цитат было недостаточно для понимания Observation 7.2.2.

[Dave Karapetian]

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

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

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

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

[a1981]

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

[Dave Karapetian]

a1981 в сообщении #1187084 писал(а):

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

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