2014 dxdy logo

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

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




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


22/09/09

1907
grizzly в сообщении #1110666 писал(а):
bin в сообщении #1110652 писал(а):
В связи с этим вопрос: автор, конечно, имеет право обозначать, как он хочет, но зачем вводить столь неудобные обозначения?
В данном случае использовано одно из стандартных обозначений (так называемая postfix notation -- можете поискать об этом). Я же могу только упомянуть один любопытный пример использования -- факториал.
Да, как программисту мне это хорошо знакомо:
Цитата:
Обра́тная по́льская нота́ция (ОПН) — форма записи математических и логических выражений, в которой операнды расположены перед знаками операций. Также именуется как обратная польская запись, обратная бесскобочная запись (ОБЗ), постфиксная нотация, бесскобочная символика Лукасевича, польская инверсная запись, ПОЛИЗ.

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

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


27/04/09
28128
Это не совсем 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 писал(а):
Да, как программисту мне это хорошо знакомо:
Обратная польская запись — это когда все операции пишутся постфиксно. А не некоторые.

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


22/09/09

1907
arseniiv в сообщении #1110679 писал(а):
Ну не сказано же там «we always write
Согласен - не сказано. И автор имеет право. Но зачем ему это нужно? Обычно и авторы, и редакторы согласны, что необходимо соблюдать однообразие в обозначениях...

BTW Попробуйте записать в "exponential нотации" эту формулу:
Цитата:
$f(n)\leq\exp(C(\log n)^{c})$
:D

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

arseniiv в сообщении #1110679 писал(а):
У нотации $a^f$ есть основания. Как раз теоретико-групповые, кажется.
А можно подробнее? Не могу представить себе таких теоретико-групповых оснований. ИМХО запись - чистая формальность. Нпр., обозначать производную точкой или штрихом с точки зрения теории этой самой производной без разницы. Но если в одном тексте то так, то так - это путает.

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


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

bin в сообщении #1110689 писал(а):
Но зачем ему это нужно?
Подождите специалистов по группам, пожалуйста. Я не помню, но где-то видел истоки $a^f$.

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


22/09/09

1907
PS Это мелочи. А по причинам солидарного молчания комментарии будут? Или м.б стоит опрос устроить:
bin в сообщении #1110652 писал(а):
1) Всем всё настолько понятно, что никто не видит необходимости говорить об очевидном.
2) Всем всё настолько не понятно, что никто ничего по существу сказать не может.
3) Все, как и я, считают свои познания в теории групп недостаточными и ждут, когда более сведущие коллеги им доступно объяснят.
;-)

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


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

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


22/09/09

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

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

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


27/04/09
28128

(Оффтоп)

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

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


22/09/09

1907

(Оффтоп)

arseniiv в сообщении #1110911 писал(а):
Прекрасно, но в цитате, на которую вы отвечали, я писал про свою мотивацию, а не про ту, которая возможна у людей. Отвечая на ваш вопрос.
Спасибо за ответ. Мне почему-то кажется, что ничто человеческое Вам не чуждо ;-)

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


27/04/09
28128

(Оффтоп)

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

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


22/09/09

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

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}$ :o Такое не часто встретишь в теоретической дискретной математике - в прикладной сколько угодно.

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.)
М.б. для кого это и очевидно, кроме автора? :shock:

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

(Оффтоп)

arseniiv в сообщении #1111210 писал(а):
Я альтруист только в том, что сам выбираю нужным, увы.
На этом форуме много нас - альтруистов. Учим школьников и студентов типовые задачки решать. А как только речь заходит о более серьезном - тут же решаем, что нам это не нужно. Истинные альтруисты - вдруг что настолько серьезное сделаем, что нам за это какие блага будут - ужжжас :D

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


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

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


08/11/11
5940
bin в сообщении #1111295 писал(а):
М.б. для кого это и очевидно, кроме автора?


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

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


22/09/09

1907
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$.

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


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

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

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



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

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


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

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