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

[bin]

grizzly в сообщении #1110666 писал(а):

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

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

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

Да, как программисту мне это хорошо знакомо:

Цитата:

Обра́тная по́льская нота́ция (ОПН) — форма записи математических и логических выражений, в которой операнды расположены перед знаками операций. Также именуется как обратная польская запись, обратная бесскобочная запись (ОБЗ), постфиксная нотация, бесскобочная символика Лукасевича, польская инверсная запись, ПОЛИЗ.

Стековой машиной называется алгоритм, проводящий вычисления по обратной польской записи (см. ниже пример вычисления выражений).
(Википедия)

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

[arseniiv]

Это не совсем postfix — скорее, exponential.

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

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

Ну не сказано же там «we always write $x^f$ for $f(x)$». Написано «we usually write». Это не единственная статья, где неоднозначности авторы доверяют читателю разобрать с помощью контекста. Если $b$ в $a^b$ не определено или не является функцией с областью определения, содержащей $a$, это знак.

-- Чт мар 31, 2016 02:40:03 --

У нотации $a^f$ есть основания. Как раз теоретико-групповые, кажется.

-- Чт мар 31, 2016 02:41:25 --

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

Да, как программисту мне это хорошо знакомо:

Обратная польская запись — это когда все операции пишутся постфиксно. А не некоторые.

[bin]

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

Ну не сказано же там «we always write

Согласен - не сказано. И автор имеет право. Но зачем ему это нужно? Обычно и авторы, и редакторы согласны, что необходимо соблюдать однообразие в обозначениях...

BTW Попробуйте записать в "exponential нотации" эту формулу:

Цитата:

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

-- Чт мар 31, 2016 00:55:54 --

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

У нотации $a^f$ есть основания. Как раз теоретико-групповые, кажется.

А можно подробнее? Не могу представить себе таких теоретико-групповых оснований. ИМХО запись - чистая формальность. Нпр., обозначать производную точкой или штрихом с точки зрения теории этой самой производной без разницы. Но если в одном тексте то так, то так - это путает.

[arseniiv]

(Будем считать, что я понял это как «перепишите все применения функций в экспоненциальной нотации в этой формуле».) Зачем?

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

Но зачем ему это нужно?

Подождите специалистов по группам, пожалуйста. Я не помню, но где-то видел истоки $a^f$.

[bin]

PS Это мелочи. А по причинам солидарного молчания комментарии будут? Или м.б стоит опрос устроить:

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

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

[arseniiv]

У меня 3. Хотя я верю, что, потратив достаточно времени, мог бы разобраться. Просто нет мотивации это делать, есть другие дела.

[bin]

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

У меня 3. Хотя я верю, что, потратив достаточно времени, мог бы разобраться. Просто нет мотивации это делать, есть другие дела.

Мотивация обычная для фундаментальной науки. История науки хранит не только имена исследователей, сделавших значительное открытие (то, что это открытие в случае признания будет значительным, похоже, никто не сомневается), но и имена исследователей, подтвердивших это открытие, а также имена исследователей, опровергших гипотезы, которые наделали много шума (то, что сейчас произошло много шума - очевидно). В сложившейся ситуации публикация рецензии (особенно если это будет развернутая рецензия) привлечет самое пристальное внимание мирового научного сообщества. Никакая статья неидеальна. Скорее всего, в результате детального изучения появятся предложения по улучшению, а может, и идеи альтернативного доказательства каких-либо теорем, приведенных в статье. И это вызовет большой интерес. Очень интересна была бы реализация предложенного алгоритма в виде программы. Такая программа с доступным исходным кодом вызвала бы очень высокий интерес. (Тем более, что долетали глухие возражения, что алгоритм описан недостаточно для реализации).

BTW А кто знает: была ли программная реализация алгоритма Лакса для изоморфизма графов с ограниченными степенями вершин? (На этом алгоритме базируется обсуждаемый подход).

[arseniiv]

(Оффтоп)

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

Мотивация обычная для фундаментальной науки. История науки хранит не только имена исследователей, сделавших значительное открытие (то, что это открытие в случае признания будет значительным, похоже, никто не сомневается), но и имена исследователей, подтвердивших это открытие, а также имена исследователей, опровергших гипотезы, которые наделали много шума (то, что сейчас произошло много шума - очевидно).

Прекрасно, но в цитате, на которую вы отвечали, я писал про свою мотивацию, а не про ту, которая возможна у людей. Отвечая на ваш вопрос.

[bin]

(Оффтоп)

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

Прекрасно, но в цитате, на которую вы отвечали, я писал про свою мотивацию, а не про ту, которая возможна у людей. Отвечая на ваш вопрос.

Спасибо за ответ. Мне почему-то кажется, что ничто человеческое Вам не чуждо

[arseniiv]

(Оффтоп)

Я альтруист только в том, что сам выбираю нужным, увы.

[bin]

Дочитал препринт до середины. Многое не понимаю и решил пока не вникать в детали, а просто посмотреть общую структуру. Но некоторые детали привлекают внимание. Интересно бы услышать комментарии.

1) В версиях v2 и v1 одно и то же доказательство:

Цитата:

Proof. The condition implies that $\mid\mathfrak{G_{m}}:G\mid<1.9^{m}$.
(v2 P.44.)

Assume $\mid\mathfrak{G_{m}}:G\mid<1.9^{m}$ (otherwise the conclusion is amply satisfied).
(v1. P.40.)

Именно $1.90^{m}$, а не $1.910^{m}$ и не $1.890^{m}$ Такое не часто встретишь в теоретической дискретной математике - в прикладной сколько угодно.

2)

Цитата:

Observation 7.2.2. In a bipartite graph the following are equivalent for vertices $x,y (x\neq y)$:

(a) $x$ and $y$ are twins;

(b) $x$ and $y$ are strong twins;

(c) $x$ and $y$ are weak twins.

Proof. Obvious.
(v2 P.45. v1. P.41.)

М.б. для кого это и очевидно, кроме автора?

-- Сб апр 02, 2016 00:45:17 --
arseniiv,

(Оффтоп)

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

Я альтруист только в том, что сам выбираю нужным, увы.

На этом форуме много нас - альтруистов. Учим школьников и студентов типовые задачки решать. А как только речь заходит о более серьезном - тут же решаем, что нам это не нужно. Истинные альтруисты - вдруг что настолько серьезное сделаем, что нам за это какие блага будут - ужжжас

[sqribner48]

По графу Джонсона есть статья (вроде что-то близкое к пояснению Аронсона про граф Джонсона )
К. В. Воробьeв, О вложении собственных функций графа Джонсона в собственные функции графа Хэмминга, Дискретн. анализ и исслед. опер., 2013, том 20, номер 5, 3–12.
Можно получить по ссылке:
http://www.mathnet.ru/links/c6fcf9ff32166d31fee4d90e80cf04f1/da742.pdf

[g______d]

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

М.б. для кого это и очевидно, кроме автора?

Выпишите здесь все три определения полностью, разберёмся.

[bin]

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

Выпишите здесь все три определения полностью, разберёмся.

v2:

Цитата:

For groups $G,H$ we write $H\le G$ to indicate that $H$ is a subgroup of $G$.
...
2.4. Twins, symmetry defect

Convention 2.4.1. Let $\Psi\subseteq\Omega$. We view $\mathfrak{G}(\Psi)$ as a subgroup of $\mathfrak{G}(\Omega)$ by extending each element of $\mathfrak{G}(\Psi)$ to act trivially on $\Omega\setminus\Psi$.

Definition 2.4.2 (Twins). Let $G\le\mathfrak{G}(\Omega)$ and $x,y\in\Omega$. We say that the points $x\neq y$ are strong twins if the transposition $\tau=(x,y)$ belongs to $G$. We say that the points $x\neq y$ are weak twins if either they are strong twins or there exists $z\notin\{x,y\}$ such that the 3-cycle $\sigma=(x,y,z)$ belongs to $G$.

[g______d]

Это не полностью, там еще какие-то $\Psi$, $\Omega$, $\mathfrak{S}$. И желательно своими словами.