Полиномиальный алгоритм изоморфизма графов

[bin]

Circiter,
полагаю, что закрыл этот вопрос (о $\mathrm{NP}$-тости задачи проверки изоморфизма графов), однако многие по-прежнему считают его открытым Факт в том, что 11 апреля исполнится год со времени публикации первой версии статьи на arXiv.org, за это время был найден ряд ошибок, была опубликована вторая исправленная версия статьи, и в скором времени я собираюсь опубликовать третью с небольшими исправлениями, но никаких фатальных ошибок в доказательстве за это время найдено не было. Уже по этому форуму можно судить, что интерес к статье не ослабевает - в среднем в день по 8 просмотров (только этой темы), однако большинство не торопится высказываться. Та же самая тенденция и на других форумах. Часть известных специалистов в области математики и computer sci. одобрили эту статью в личной переписке (некоторые из них указаны в благодарностях в статье), но никто из них не хочет высказываться публично, они сомневаются, что в современных условиях возможно признание решения этой проблемы. Эта общая ситуация в современной математике хорошо описана в книге М. Клайн Математика. Утрата определённости. — М.: Мир, 1984.

[Pavia]

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

[bin]

Pavia,
Да, признаю, что я собирался сделать такой перевод – точнее, не перевод, а пересказ, потому что очень не люблю переводов и пишу сразу на языке публикации (русском или английском, другими не владею), пытаясь выбрать наиболее оптимальные для данного языка конструкции, исходя из известной истины, что перевод всегда уступает оригиналу. Но следующие сомнения и проблемы пока не дают мне выполнить это обещание с русскоязычной версией статьи.

1) Отсутствие поддержки. Проработав 25 лет в системе РАН, я хорошо знаю, как не просто бывает получить финансирование для исследования в области фундаментальной науки. Однако многие мои, гораздо менее значимые, исследования не всегда просто, но получали необходимую поддержку. В случае же данного исследования никто из наших и из многочисленных международных фондов не рвется оказать хоть какую-то помощь. Данная ситуация свойственна для попыток решения открытых проблем и хорошо объясняется в книге Клайна, которую я упомянул в предыдущем посте. Т.о., я сейчас не могу тратить все свое время на решение только этой проблемы. Конечно же, это не помешало бы мне пересказать статью на другом языке, однако пересказ нужно еще и поддерживать, синхронно обновляя версии, а еще нужно поддерживать программу, реализующую алгоритм, т.к. она, к сожалению, пока еще также не свободна от ошибок, возникших при программировании. В предыдущих постах я сказал, что буду скоро делать третью версию статьи, если бы изначально была и русская версия, то вместо трех версий было бы три пары – т.е. уже шесть версий. Не уверен, что в данной ситуации стоит так отвлекать силы на поддержание еще и русской версии, м.б., стоит сосредоточиться на одной – английской.

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

3) Как и многие старожилы Интернета (в сети с начала 90х), я хорошо знаю, что сетевая публика очень разная. Но в целом она достаточно доброжелательная, несмотря на то, что попадаются и неадекватные личности, обиженные на весь мир и пытающиеся кусать все подряд, и просто хамы. Еще большая доброжелательность проявляется на профессиональных форумах. Однако это верно, пока речь не заходит об открытых проблемах. В случае обсуждения решения любой из таких проблем общее отношение становится, в лучшем случае, настороженно нейтральным, и на его фоне особенно ярко проявляются отдельные личности, которые всеми силами хотят растоптать тебя с твоим решением. – Объяснение этому факту все в той же книге Клайна, а здесь это факт отмечаю потому, что существование двух версий на двух языках даст возможность таким личностям выискивать разночтения, придираясь буквально к каждой запятой. Учитывая, что в русском и в английском пунктуация, мягко говоря, сильно не совпадает, возможностей для подобных придирок будет более, чем достаточно

[upsetter]

bin, вот вы всё баламутите и баламутите.
Я с пол-пинка нашел 2 изоморфных графа для которых mt2gi1.2.4.exe
выдает GI not found
Ну шо толку от всех ваших пространных объяснений и пояснений,
и пояснений к пояснениям

[bin]

upsetter, это Вы баламутите: версия 1.2.4 устарела, используйте MT2GI v 1.4.2. Если найдете такие графы – приведите их списки смежности здесь, я проверю с пол-пинка шо толку в Вашем первом сообщении на dxdy.

[upsetter]

17
01101000110001011
10110100011000101
11011010001100010
01101101000110001
10110110100011000
01011011010001100
00101101101000110
00010110110100011
10001011011010001
11000101101101000
01100010110110100
00110001011011010
00011000101101101
10001100010110110
01000110001011011
10100011000101101
11010001100010110

00000101101011110
00111001000110110
01001110001101100
01001101110000101
01110000111001010
10110011010001100
00100101011100011
11010110100100010
10011001001101001
00011110000011011
10101010100000111
01100011100011001
11000000010101111
10101100110110000
11110100001010001
11001011011010000
00010010111110100

1-2,1-3,1-5,1-9,1-10,1-14,1-16,1-17,2-3,2-4,2-6,2-10,2-11,2-15,2-17,3-4,3-5,3-7,3-11,3-12,3-16,4-5,4-6,4-8,4-12,4-13,4-17,5-6,5-7,5-9,5-13,5-14,6-7,6-8,6-10,6-14,6-15,7-8,7-9,7-11,7-15,7-16,8-9,8-10,8-12,8-16,8-17,9-10,9-11,9-13,9-17,10-11,10-12,10-14,11-12,11-13,11-15,12-13,12-14,12-16,13-14,13-15,13-17,14-15,14-16,15-16,15-17,16-17

1-6,1-8,1-9,1-11,1-13,1-14,1-15,1-16,2-3,2-4,2-5,2-8,2-12,2-13,2-15,2-16,3-5,3-6,3-7,3-11,3-12,3-14,3-15,4-5,4-6,4-8,4-9,4-10,4-15,4-17,5-9,5-10,5-11,5-14,5-16,6-7,6-8,6-10,6-14,6-15,7-8,7-10,7-11,7-12,7-16,7-17,8-9,8-12,8-16,9-11,9-12,9-14,9-17,10-13,10-14,10-16,10-17,11-15,11-16,11-17,12-13,12-14,12-17,13-14,13-15,13-16,13-17,15-17

-- Пт апр 15, 2011 07:13:08 --

bin, у меня конечно 1.4.2. Я просто спутал.


MT2GI v 1.4.2.beta
>> Algorithm 1 RN (implementation via rational numbers usage)
>> Input:
>> Graph 1:
1-2,1-3,1-5,1-9,1-10,1-14,1-16,1-17,2-3,2-4,2-6,2-10,2-11,2-15,2-17,3-4,3-5,3-7,3-11,3-12,3-16,4-5,4-6,4-8,4-12,4-13,4-17,5-6,5-7,5-9,5-13,5-14,6-7,6-8,6-10,6-14,6-15,7-8,7-9,7-11,7-15,7-16,8-9,8-10,8-12,8-16,8-17,9-10,9-11,9-13,9-17,10-11,10-12,10-14,11-12,11-13,11-15,12-13,12-14,12-16,13-14,13-15,13-17,14-15,14-16,15-16,15-17,16-17
>> Graph 2:
1-6,1-8,1-9,1-11,1-13,1-14,1-15,1-16,2-3,2-4,2-5,2-8,2-12,2-13,2-15,2-16,3-5,3-6,3-7,3-11,3-12,3-14,3-15,4-5,4-6,4-8,4-9,4-10,4-15,4-17,5-9,5-10,5-11,5-14,5-16,6-7,6-8,6-10,6-14,6-15,7-8,7-10,7-11,7-12,7-16,7-17,8-9,8-12,8-16,9-11,9-12,9-14,9-17,10-13,10-14,10-16,10-17,11-15,11-16,11-17,12-13,12-14,12-17,13-14,13-15,13-16,13-17,15-17
>> Number of vertices is 17
>> Number of edges is 68
>> GI test: started 15.04.2011 6:12:35
>> GI not found
>> GI test: finished 15.04.2011 6:12:37
Time is 1,81199982762337 sec.
DebugFlag=0
maxBISize=6
>> End -------------------------------

-- Пт апр 15, 2011 07:21:05 --

поверьте, бин, я не тот человек чтобы над чем-то ехидно злорадствовать и т.д. Но вот что думать и делать, если человек 5 лет носится со своим поли-таймом, а у него на 5-ом графе моих тестов полный конфуз. Я же не спецом подбирал, взял из сильно однородных и других довольно трудных. А этот граф - это граф Палея. Вот его особенность (совпадение с комплементом) всё и испортили.

[bin]

upsetter, прежде всего должен напомнить Вам, что Вы пишете на научный форум, и у нас здесь обсуждение, а не базарная склока, и я не "ношусь 5 лет", а обсуждаю и делаю исправления в алгоритме, по мере необходимости. Уверен, что Вам не удастся найти ученого совета, которому бы понравились выражения типа "носится", "с пол-пинка" и "шо толку". Поэтому смените, пожалуйста, лексику и придерживайтесь общепринятых норм вежливости и норм ведения научной дискуссии.

В отношении графа Палея - я знаю этот граф, он знаменит также тем, что является грациозным. Вот результат для сравнения с Вашим:

MT2GI v 1.4.2.beta
>> Algorithm 1 FP (implementation via floating points usage; fast, but may have rounding errors)
>> Input:
>> Graph 1:
1-2,1-3,1-5,1-9,1-10,1-14,1-16,1-17,2-3,2-4,2-6,2-10,2-11,2-15,2-17,3-4,3-5,3-7,3-11,
3-12,3-16,4-5,4-6,4-8,4-12,4-13,4-17,5-6,5-7,5-9,5-13,5-14,6-7,6-8,6-10,6-14,6-15,7-8,
7-9,7-11,7-15,7-16,8-9,8-10,8-12,8-16,8-17,9-10,9-11,9-13,9-17,10-11,10-12,10-14,11-12,
11-13,11-15,12-13,12-14,12-16,13-14,13-15,13-17,14-15,14-16,15-16,15-17,16-17
>> Graph 2:
1-6,1-8,1-9,1-11,1-13,1-14,1-15,1-16,2-3,2-4,2-5,2-8,2-12,2-13,2-15,2-16,3-5,3-6,3-7,
3-11,3-12,3-14,3-15,4-5,4-6,4-8,4-9,4-10,4-15,4-17,5-9,5-10,5-11,5-14,5-16,6-7,6-8,6-10,
6-14,6-15,7-8,7-10,7-11,7-12,7-16,7-17,8-9,8-12,8-16,9-11,9-12,9-14,9-17,10-13,10-14,
10-16,10-17,11-15,11-16,11-17,12-13,12-14,12-17,13-14,13-15,13-16,13-17,15-17
>> Number of vertices is 17
>> Number of edges is 68
>> GI test: started 15.04.2011 16:50:51
>> GI found:
1-1, 2-13, 3-16, 4-2, 5-8, 6-12, 7-7, 8-3, 9-6, 10-14, 11-10, 12-5, 13-4, 14-9, 15-17,
16-11, 17-15,
>> GI test: finished 15.04.2011 16:50:51
Time is 0 sec.
DebugFlag=0
>> End -------------------------------

Т.о. реализация в рациональных числах дала неверный результат, а реализация того же алгоритма с плавающей запятой дала верный. Это может означать, что в библиотеке рациональных чисел баг. В ближайшее время постараюсь его найти и обновить версию программы.

Кстати о багах, даже софт этого форума, несмотря на долгую и интенсивную эксплуатацию, от багов не свободен: обратите внимание на сбой формата в Вашем сообщении - ту же трудность я испытал в этом сообщении: при длинных строках вида: "а-б,с-д,..." формат нарушается. Но никто не говорит, что это "полный конфуз" А 5-ый граф или 335-ый - объяснимо просто: у всех свои любимые графы, кто-то не найдет бага и с очень большим набором, а кто-то найдет сразу в другом наборе. Для этого такие обсуждения и ведутся.

[upsetter]

"научный форум"? Это нонсенс. Это все равно что "научная пивнушка".
Понимаете, я вот уверен, что вы всё и без подсказок со стороны про свой алгоритм знаете. Т.е., вы осознанно дурите людям головы.

[Toucan]

upsetter, предупреждение за недопустимые формы ведения дискуссии.

[upsetter]

Тов. Модератор, я всё понял, чай не дурак.

[bin]

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

[bin]

Посмотрел гугл и обнаружил, что 4 апреля на сайте cstheory.stackexchange.com Vitali V. Valiayeu (Гомель, Белорусия) под ником trg787 опубликовал тот же самый пример, с графом Палея-17. Далее не могу не процитировать обращения к одному из моих критиков:
«David ;; David, I see you are an expert. Could you be so kind, in your some spare time, to check my utility for GI testing? It's at […] It's in C++, very simple, easy to compile, easy to run. And it's... polynomial-time and due to this it's very fast (refuting its algorithm would be a great result for me). Btw on Siberian graphs MT2GI-1.4.2 ran for ~60(s) - too slow to my taste.»
Интересно: 1) в моей статье указан email, но никто из участников обсуждения на cstheory.stackexchange.com не потрудился сообщить мне – автору, что они критикуют мою статью. Воля ваша, но смотрится такое как-то мелко-пакостно; 2) я и здесь, и на других форумах отказываюсь обсуждать конкурирующие работы, чтобы не получать упреков в пристрастности – вижу, что мои «противники» не столь благородны 3) на упомянутом выше сайте я уже задал вопрос trg787(Vitali V. Valiayeu), не работает ли он здесь под ником upsetter? Здесь адресую этот же вопрос участнику с ником upsetter: не Вы ли Vitali V. Valiayeu?

[ha]

Вам нужны ошибки? Первая находится уже на странице 7. Conclusion 2 не верно или по крайней мере не доказано. Чтобы сделать его верным нужно дополнительно потребовать, что существует хотя бы один изоморфизм между графами переводящий $i$ в $j$.

Другой вопрос используется ли это утверждение в вашей статье. Если нет, то его как и все остальные не используемые утверждения нужно из статьи выкинуть, потому что уже не в первый раз в них находятся ошибки.

[ha]

Ссылка на Conclusion 2 из леммы 1 в начале 9-той страницы - полный бред. Написанное не имеет никакого к ней отношения. Смысл написанного тоже не совсем понятен. Лично я понял это как то, что можно выбрать такой вектор b, что x_i будут различными. Это очевидно и не нуждается в Conclusion 2.
Зачем помещать эти рассуждения не туда, где они используются - для меня загадка.

Дальше ошибка в том, что $d_h=d_{r(h)}$. Уравнение (5) не имеет к нему никакого отношения. возможно имелось в виду формула $\sum_{h=1}^n k_{hi}=d_i+1$, но она суммирует не по строкам, как нам надо, а по столбцам. Эту проблему можно, впрочем, решить прицепив степени вершин к инварианту.

А вот на следующей строчке ошибка уже фатальна. Утверждать, что $k_{lh}=k_{r(l)r(h)}$ вы не можете. Можно только писать, что $k_{ip} = k_{pi}$, а вот, к примеру, доказательства $k_{ii} = k_{pp}$ у вас нет.

Вот наглядный пример:$\begin{bmatrix} c & a & e & d \\ a & d & c & e \\ e & c & d & b \\ d & e & b & c\end{bmatrix}$. $r(1) = 2,\ r(2) = 1,\ r(3) = 4,\ r(4) = 3$. Считайте, что граф регулярный, откуда матрицы $A$ и $A^{-1}$ симметричны. Мы видим, что отсортированная первая и вторая строка совпадают. Аналогично третья и четвертая. Тем не менее $k_{ij} = k_{r(i)r(j)}$ не верно.

Если вы докажете этот факт, то вам даже не будет нужно не доказанное вами Conlusion 2. Поскольку факт равносилен $A^{-1} = R^{-1}\cdot A^{-1}\cdot R$, откуда следует аналогичное равенство для $A$, а это и есть фактически наш граф. Поэтому $R$ является автоморфизмом графа $G$, что нам и нужно для леммы 1.

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

[Toucan]

ha в сообщении #437305 писал(а):

Ссылка на Conclusion 2 из леммы 1 в начале 9-той страницы - полный бред.

ha,
замечание за недопустимые формы обсуждения научной статьи. В дальнейшем постарайтесь, пожалуйста, избегать подобных формулировок.