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

[drozdov_mihail]

Вообще говоря, интересно проверить эффективность алгоритма (а заодно и его "правильность") на высокосимметричных молекулярных системах, например, с максимально возможной симметрией Ih: без труда можно построить такие системы, содержащие 1000-и атомов.

[whitefox]

2drozdov_mihail
В контексте проблемы изоморфизма вопрос эффективности ставится в следующей форме:
принадлежит эта задача классу $\textrm P$ или нет?

А насчёт "правильности", ТС утверждает, что с "химическими" задачами его алгоритм справляется без ошибок. Вопрос в том будет ли он так же правильно работать и в общем случае? Для предыдущих вариантов алгоритма ответ -- нет. А новый вариант пока ещё не представлен.

[bin]

whitefox в сообщении #470382 писал(а):

Для решения проблемы изоморфизма графов сам изоморфизм находить не обязательно.

Теоретически не обязательно, а практически желательно. Для проверки алгоритма, например. Если посмотреть аналогичные работы - почти во всех не останавливаются на вопросе "изоморфны ли графы?", но и пытаются найти какой-то изоморфизм.

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

Цитата:

Consider, what effect for solutions of system (1) may be caused by a change of one of absolute terms. Let the absolute term $B_{i}$ be increased by $\Delta B>0$. Then the process of solutions changing may be described by following model. Firstly, note that the sum of solutions increases by $\Delta B$, because of Property 2. Consider, how this increment is distributed. First of all, the increase of $B_{i}$ causes increase of $x_{i}$ by $\Delta x_{i}=\Delta B/(d_{i}+1)$. Further, $i$-adjacent vertex $k$ also increases its own weight by $\Delta x_{i}/(d_{k}+1)$. However, the first approximation of increment of $x_{k}$ is only part of the increment of $x_{i}$:

$$ \Delta x_{k}=\frac{\Delta x_{i}}{d_{k}+1}=\frac{\Delta B}{(d_{i}+1)(d_{k}+1)}<\frac{\Delta B}{d_{i}+1}=\Delta x_{i}.$$

At the same time, increase of neighbors number, i.e. increase of $d_{i}$, causes decrease of the weight's increment of every of these neighbors. Also, every increase of weight of every $i$-adjacent vertex, causes additional increase of weight of vertex $i$, but this addition is smaller part $\Delta x_{k}/(d_{i}+1).$ Similar situation we observe for vertices that are more remote from $i$ vertex. For example, for $k$-adjacent vertex $p$ that is not $i$-adjacent vertex, the first approximation of increment of its weight is $\Delta x_{k}/(d_{p}+1).$ The vertex $p$ may be connected with a few $i$-adjacent vertices that vertices have equal weight $x_{k}$ (maximum allowed for $k$-adjacent vertex), but in this case the increment for vertex $p$ will be less than the increment for vertex $k:$

$$ \frac{d_{p}\Delta x_{k}}{d_{p}+1}<\Delta x_{k}.$$

From here we get the following property 4 of system (1).
Property 4. The increase of $B_{i}$ by $\Delta B$ increases every solution $x_{j}$ (where $j=1,{\ldots{}},n$) of system (1) by $\Delta x_{j}$, where $0<\Delta x_{j}<\Delta B.$

2) Arthur Rubin прислал мне следующее доказательство:

Цитата:

Clean description of property 4, with proof:
Property 4: If $B\ensuremath{\ge}0$ (coordinatewise),
(a): $x\ensuremath{\ge}0$ (coordinatewise)
(b): If, in addition, $B\ensuremath{\neq}0$, then $\Delta x>0$(coordinatewise)
(c): $\max (x)\ensuremath{\le}\max (B)$
(d): If, in addition, $B$ is not constant, than $\max (x) <\max (B)$
Proof: Let $M$ be the modified incidence matrix, so that equation (1) can be written as $x = Mx + b$. Clearly $M$ is substocastic (all entries are non-negative, and all row sums are less than 1), so that the normal power series expansion $\left(I-M\right)^{-1}=\sum_{n=0}^{\infty}M^{n}$ converges. In addition, as the graph is connected, for any two vertices, there is a path between them. Let $k$ be the maximum of those path lengths. Then $\sum_{n=0}^{k}M^{n}$ has all entries positive.

Proof of specific properties, noting that $\left(I-M\right)x=b$, so $x=\left(I-M\right)^{-1}b$. (a): $\left(I-M\right)^{-1}\geq0$ (coordinate-wise), by inspection (b): $\left(I-M\right)^{-1}=\sum_{n=0}^{\infty}M^{n}\geq\sum_{n=0}^{k}M^{n}$, so all components are greater than 0. (c) The increment from $B$ to the vector with all components $\max (B)$ satisfies the initial property of this Proposition, so (a) applies to that property. But, by Property 3, the the increment corresponding to the vector with all components $\max (B)$ is that same vector, so that (a) reads that $x \ensuremath{\le} $ the vector which is all $\max (\Delta B)$, component-wise. Hence $\max(x)\ensuremath{\le}\max(B)$. (d) Using property (b) for the increment, leads to $\max(x)<\max(B)$ if $B$ is not a constant vector. QED

This seems stronger than your existing Property 4.
An alternative formulation would be: $\min(B)\ensuremath{\le}\min(x)\ensuremath{\le}\max(x)\ensuremath{\le}\max(B)$, and if any inequality is proper, then all are.

3) Будем задавать начальный вес, равный единице, вершине, которую мы назовем вершиной-источником, а остальным вершиным графа зададим начальные веса, равные нулю. Решив СЛУ, мы увидим, что все вершины графа приобрели положительный вес, причем он убывает с изменением расстояния от вершины-источника. Если два соседа вершины-источника имеют одинаковые степени и одинаковый вес, они могут оказаться подобными, но если у них разный вес, то они точно не могут быть подобными. Функцию Comp мы можем использовать для поиска автоморфизма между указанной в ее параметрах парой вершин одного из графов. Будем искать тождественную подстановку 1-1,... Очевидно, что только пары подобных вершин дадут подходящие биграфы в функции Comp. И никакое несовпадающее решение не приведет к пустому множеству пересечений ребер подходящих биграфов. Т.к. Comp работает с отсортированными координатами векторов решений, то результат ее работы не зависит от нумерации вершин графа. Значит, Comp будет выдавать правильный список подобных вершин, когда на ее входе указаны две подобные вершины (для изоморфных графов).

-- Пт июл 22, 2011 19:05:04 --

drozdov_mihail в сообщении #470463 писал(а):

Вообще говоря, интересно проверить эффективность алгоритма (а заодно и его "правильность") на высокосимметричных молекулярных системах, например, с максимально возможной симметрией Ih: без труда можно построить такие системы, содержащие 1000-и атомов.

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

[whitefox]

2bin
Некоторое время меня не будет.
Прошу не считать моё молчание за согласие.

[ha]

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

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

Ну и цитата с блога http://experimentalmath.info/

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

Там блог один. Вот прямая ссылка - http://experimentalmath.info/blog/2011/ ... -of-doubt/.

Цитата:

-- Пн июл 18, 2011 14:57:17 --
Намедни Вы признали:

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

Этот алгоритм вроде правильный. Теперь попробуйте его доказать.

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

Результат считается полученным, когда признают доказательство автора. Пока что вы его даже не предъявили. Не говоря уж о том, что результат в виду простоты формулировки и не сложности доказательства должен быть давно известен специалистам. Если вы у них спросите доказательство и скопируйте его (или ссылку на статью, где он упоминается) сюда, то к вам не будет никаких претензий. Почему вы пытаетесь доказать его самостоятельно, демонстрируя уйму тривиальных ошибок (поиск в ширину? ну соедините первую вершину со всеми остальными и он вам ничего не даст) мне не понятно.

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

Цитата:

-- Пн июл 18, 2011 15:09:34 --

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

Да, это проблема меньшего масштаба. Тем не менее людей интересующихся математикой достаточно много.

Цитата:

-- Пн июл 18, 2011 15:25:53 --

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

Теория сложности вычислений - это часть математики. А задача изоморфизма графов ей принадлежит. Поэтому доказательства в ней должны следовать всем требованиям строгости устоявшимся в математике, а не программировании.

Теория сложности вычислений - это часть computer sci., как и программирование. Но речь была не про то, что "доказательства в ней должны следовать всем требованиям строгости устоявшимся в математике", а про то, что программирование наиболее явно свидетельствует о природной склонности людей, и даже лучших специалистов, делать везде, где только возможно, ошибки, и даже тривиальные. Это "зашито" в человеческой природе и с этим приходится считаться при решении сложных задач, и без толку взывать "не делайте ошибок" даже в лучшей бригаде программистов (куда нередко входят и чистые математики) - все равно сделают! Поэтому реалисты всегда планируют комплексы сложных мероприятий по устранению ошибок. А у Вас нереалистичный подход, применимый только для хорошо решающихся задач.

Это "зашито" в программировании. А в математике и в теории сложности вычислений в частности ситуация другая.

Цитата:

-- Пн июл 18, 2011 15:35:16 --

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

вы просили показать существование чего-либо без ошибок, а теперь говорите, что не все книги по математике без ошибок.

Нет, я не просил, это Вы заявили "Я прочел множество книг по математики и в них почему-то не было тривиальных ошибок" (это прозвучало как "все книги"), а теперь согласились, что не все книги по математике без ошибок, поменяв таким образом квантор

[/quote]
Для меня это как "все книги" не звучит. Так что дело лишь в вашем неправильном понимании.

-- Пн июл 25, 2011 13:30:01 --

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

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

Клайн разве считает, что в математике нужны доказательства с тривиальными ошибками?

А я разве говорил, что в математике нужны доказательства с ошибками?

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

Цитата:

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

А практика математики демонстрирует, что важна не трудность задачи, а трудность решения.

Цитата:

А значит, и надо подходить как в программировании: методом последовательного исправления версий. Что, кстати, математики и делают, посмотрите препринт http://arxiv.org/abs/0907.3965 - там уже 43 версии! Вот так и надо работать, а не стенать по поводу ошибок в промежуточных версиях.

Последовательное исправление версий работает тогда, когда путь к решению ясен (что почти всегда выполнено в программировании). А в математике ситуация другая. Можно сколько угодно затыкать дырки, но если идея не та, то будут образовываться новые и решения никогда не получится. Так что эти 43 версии ничего хорошего не говорят. Если у авторов до сих пор ничего доказать не получилось (надо смотреть подробно, есть ли там важные промежуточные результаты), значит скорее всего их идея сама по себе задачу не решает.

Цитата:

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

Все остальные, как показывает приведенная мною цитата, считают, то теория Лакатоса применима исключительно к 17-18 веку, а вы демонстрируете не знание базовых основ модельного подхода, считая, что если она работает 2 века, то работает везде.

Я уже спрашивал, откуда та цитата? Вы не ответили. Но если бы все так считали, как Вы, то эта книга никогда бы не стала такой известной. Кому сейчас нужна модель для 18 века, кроме узкого круга историков?

Во-первых, это очень интересный этап развития математики. В этих веках практический подход преобладал над теоретическим. Во-вторых, эта теория является часть более общей теории Лакатоса, которая относится к остальным естественным наукам и в этом случае она сохраняет популярность до сих пор.

Цитата:

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

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

Хорший математик никогда бы не взялся за решение такой задачи (на это и сетует Клайн), я же себя позиционирую не как математик, а как computer scientist Никто, кроме Вас, эту тему закрыть не предлагал (можете видеть, что пустые темы администрация этого сайта закрывает очень быстро, никого не спрашивая, а моя тема давно и в топе по количеству просмотров),

Кому-то надо быть первым. Практически никто кроме меня не читал вашу статью. Из тех кто читал, положительных отзывов нет. Это единственное, что имеет значение.

Цитата:

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

Не вижу ни одного человека соглашающегося с вашей методологией.

Цитата:

(Скажу по секрету, что даже никто из отвергнувших мою статью редакторов на прямой вопрос "не считает ли он, что мне не стоит продолжать попытки решения этой проблемы" не ответил, что "мне не стоит продолжать".) Т.о резюмируя сказанное, я прихожу к выводу, что используемая методология себя оправдывает и иначе эту проблему не решить.

Чтобы она себя оправдывала, она должна работать. Пока что мы видим годы обсуждений и нулевой результат.

Цитата:

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

Конструктивное обсуждение - это приведение доказательств без тривиальных ошибок. Оформляйте, пожалуйста, ваши неправильные доказательства с множеством тривиальных ошибок как оффтопик, чтобы не замусоривать тему рассуждениями не по существу.

[ha]

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

Судя по отсутствию конретной критики, претензий к доказательствам предложенных двух алгоритмов поиска изоморфизма по списку псевдо-подобных вершин не осталось?

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

[bin]

ha

(Оффтоп)

ну я же уже просил оформлять вопросы регламента как оффтопик!

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

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

Прошло уже несколько десятков лет, как эта проблема (GI) в списке открытых, а никаких продвижений нет и не видно на горизонте Хорошо ее решает мат.сообщество! Если некоторые важные проблемы не решаются, то у любого, даже у стороннего, наблюдателя появится мнение, что не так их решают. Тем более о проблемах математической самоизоляции, из-за которой и не решают подобные проблемы, говорят не только сторонние наблюдатели, но и сами математики! А продвижения в моем решении налицо. Задача GI свелась к системе общих представителей.

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

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

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

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

Это "зашито" в программировании. А в математике и в теории сложности вычислений в частности ситуация другая.

Чем же это она другая? Только тем, что в чистой математике ограничиваются решением хорошо решающихся задач.

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

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

Однако это прозвучало как "все книги, которые я прочел". Дело в Вашем нежелании (или неумении) ясно излагать свои мысли. Вот Вы говорите "Для меня это не звучит" - а важно не то, как звучит для Вас, важно, как это звучит для собеседника и аудитории, к которым Вы обращаетесь. А обоснование, как Ваши слова Вам же понятны - смехотворно, во-первых, и демонстрирует Ваше пренебрежение аудиторией, во-вторых. Подумайте над этим! Когда и если будете выступать, например, перед ученым советом на защите собственной диссертации, никогда не говорите таких слов!

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

Не говоря уж о том, что результат в виду простоты формулировки и не сложности доказательства должен быть давно известен специалистам. Если вы у них спросите доказательство и скопируйте его (или ссылку на статью, где он упоминается) сюда, то к вам не будет никаких претензий. Почему вы пытаетесь доказать его самостоятельно, демонстрируя уйму тривиальных ошибок (поиск в ширину? ну соедините первую вершину со всеми остальными и он вам ничего не даст) мне не понятно.

Вы специалист? Вам известно доказательство? Дайте, пожалуйста, ссылку. Ваш контрпример относится к алгоритму 2 (я подумаю над улучшением). Ошибок в алгоритме 1 и его доказательстве Вы, похоже, не нашли.

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

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

Про (псевдо)-подобные и про два доказательства двух различных решений читайте внимательнее предыдущие сообщения.

[ha]

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

3) Будем задавать начальный вес, равный единице, вершине, которую мы назовем вершиной-источником, а остальным вершиным графа зададим начальные веса, равные нулю.

Где будем?

Цитата:

Решив СЛУ, мы увидим, что все вершины графа приобрели положительный вес, причем он убывает с изменением расстояния от вершины-источника.

Вчитываемся в свойство 4 - никаких расстояний там нет. Опять тривиальная ошибка. И главное все равно это никак не используется, так зачем писать? Я вижу только одну причину - намеренно усложнить построение контрпримеров. Чем больше условий, которые никак не используются в доказательстве, тем сложнее построить контрпример. Примечательно, что математики как раз всегда стараются сделать свои утверждения как можно более общими, чтобы получить как можно более сильные результаты.

Цитата:

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

Никак не используется в дальнейшем. Зачем тогда писать?

Цитата:

Функцию Comp мы можем использовать для поиска автоморфизма между указанной в ее параметрах парой вершин одного из графов.

Если можем, то задача решена, больше писать ничего не нужно. Или дальнейшее это типа "доказательство"?

Цитата:

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

Не запутались в отрицаниях? Пустое множество пересечений на совпадающих решениях звучит как опечатка, что бы эти пересечения и решения не значили. Что означают "подходящие биграфы"?

Цитата:

Т.к. Comp работает с отсортированными координатами векторов решений, то результат ее работы не зависит от нумерации вершин графа. Значит, Comp будет выдавать правильный список подобных вершин, когда на ее входе указаны две подобные вершины (для изоморфных графов).

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

[bin]

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

Где будем?

В доказательстве.

-- Пн июл 25, 2011 13:44:55 --

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

Вчитываемся в свойство 4 - никаких расстояний там нет. Опять тривиальная ошибка.

Это опечатка. См. фрагмент перед свойством 4:

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

Напомню следующий фрагмент из первой версии препринта

[ha]

Цитата:

Ошибок в алгоритме 1 и его доказательстве Вы, похоже, не нашли.

Если вы имеете в виду Comp - то я его подробно не читал. Сразу видно, что оно справедливо для любой $f(G)$, а значит можно его существенно упростить за счет подстановки $f(G)=M$. После чего будет либо найдено решение изоморфизма графов в десять строчек (а значит оно давным давно было бы найдено), либо найдется множество тривиальных ошибок.

[bin]

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

Что означают "подходящие биграфы"?

Те которые не содержат неподходящее множество ребер:

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

Если найдется вершина $k$, не имеющая ребер в множестве $E$, то будем называть такое множество неподходящим. Очевидно, что для неподходящего множества невозможно найти решений, удовлетворяющих Утверждению 3. Поэтому если множество ребер биграфа $H_{ij}$ образует при пересечении с множеством ребер биграфа $H_{0}$ неподходящее множество, то будем удалять биграф $H_{ij}$ из дальнейшего рассмотрения и ребро $(i,j)$ из $H_{0}$.

-- Пн июл 25, 2011 13:53:58 --

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

Сразу видно, что оно справедливо для любой

Мне не видно Тут два момента: 1) сведение GI к системе общих представителей (СОП), 2) конкретный алгоритм поиска СОП. Если в (2) ошибка, это не значит, что (1) неверно. BTW алгоритма (2) поиска СОП я в литературе пока не нашел.

-- Пн июл 25, 2011 13:58:24 --

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

Если можем, то задача решена, больше писать ничего не нужно. Или дальнейшее это типа "доказательство"?

Да, набросок доказательства.

[ha]

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

ha
Про (псевдо)-подобные и про два доказательства двух различных решений читайте внимательнее предыдущие сообщения.

Я их внимательно читаю. Но никаких окончательных версий не вижу.

[bin]

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

Сразу видно, что оно справедливо для любой $f(G)$, а значит можно его существенно упростить за счет подстановки $f(G)=M$.

И какие будут отсортированные координаты при такой замене? Для регулярных графов все векторы одинаковы? При чем тут Утверждение 3? $f(G)=M$ - вырожденный случай! Какие биграфы мы получим? Полные?

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

Т.к. Comp работает с отсортированными координатами векторов решений, то результат ее работы не зависит от нумерации вершин графа.

-- Пн июл 25, 2011 14:18:24 --
ha

(Оффтоп)

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

никаких окончательных версий не вижу

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

-- Пн июл 25, 2011 14:34:56 --

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

Цитата:

Ошибок в алгоритме 1 и его доказательстве Вы, похоже, не нашли.

Если вы имеете в виду Comp - то я его подробно не читал.

Нет. Речь про

whitefox в сообщении #469517 писал(а):

Тогда Ваш алгоритм можно представить так

и далее.

-- Пн июл 25, 2011 15:07:56 --

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

Цитата:

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

Никак не используется в дальнейшем. Зачем тогда писать?

Из этого с очевидностью следует, что вес зависит от подобия, что биграфы будут разными, в том числе и неподходящими. Для иного инварианта такого может не быть и Comp работать не будет.

[bin]

ha

(Оффтоп)

PS Вы никак не хотите признать очевидности, что в науке имеют значение не только окончательные версии. С Вашей точки зрения гипотезе Улама нет места в серьезных книгах, т.к. она не доказана и является только правдоподобным утверждением. Однако же его растиражировали, а Харари еще добавил слабую форму ;-)

-- Пн июл 25, 2011 15:38:58 --

ha

(Оффтоп)

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

Последовательное исправление версий работает тогда, когда путь к решению ясен (что почти всегда выполнено в программировании)

Нет! почти всегда НЕ выполнено в программировании нетривиальных задач. Примеры: OS, AI, компиляторы C++, квантовая и математическая химии.

[bin]

ha

(Оффтоп)

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

Цитата:

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

Все остальные, как показывает приведенная мною цитата, считают, то теория Лакатоса применима исключительно к 17-18 веку, а вы демонстрируете не знание базовых основ модельного подхода, считая, что если она работает 2 века, то работает везде.

Я уже спрашивал, откуда та цитата? Вы не ответили. Но если бы все так считали, как Вы, то эта книга никогда бы не стала такой известной. Кому сейчас нужна модель для 18 века, кроме узкого круга историков?

Во-первых, это очень интересный этап развития математики. В этих веках практический подход преобладал над теоретическим. Во-вторых, эта теория является часть более общей теории Лакатоса, которая относится к остальным естественным наукам и в этом случае она сохраняет популярность до сих пор.

1) Век Вы перепутали: не только 18, но и 19 (см. c.2 аннотацию); 2) но и 20 - много ссылок на ученых двадцатого века (работы Пуанкаре, Тарского, Полья, Поппера, Бэртли); 3) цель четко указана в авторском введении (прочтите хотя бы его!):

Цитата:

Целью этих статей является подход к некоторым проблемам методологии математики. […] Недавняя экспроприация термина «методология математики» для использования в качестве синонима «метаматематики» имеет несомненно формалистский привкус. Это показывает, что в формалистской философии математики нет настоящего места для методологии как логики открытия. […]Цель этого этюда и есть этот вызов математическому формализму, но это не прямой вызов основным положениям математического догматизма. Наша скромная цель состоит в установлении положения, что неформальная квазиэмпирическая математика не развивается как монотонное возрастание количества несомненно доказанных теорем, но только через непрерывное улучшение догадок при помощи размышления и критики, при помощи логики доказательств и опровержений. Поскольку, однако, метаматематика представляет парадигму неформальной квазиэмпирической математики и в настоящее время находится в быстром росте, то эта статья тем самым бросает вызов современному математическому догматизму. С.7-10

Тоже самое Вы могли бы прочесть и в Википедии:

Цитата:

Proofs and Refutations is a book by the philosopher Imre Lakatos expounding his view of the progress of mathematics. The book is written as a series of Socratic dialogues involving a group of students who debate the proof of the Euler characteristic defined for the polyhedron. A central theme is that definitions are not carved in stone, but often have to be patched up in the light of later insights, in particular failed proofs. This gives mathematics a somewhat experimental flavour. At the end of the Introduction, Lakatos explains that his purpose is to challenge formalism in mathematics, and to show that informal mathematics grows by a logic of "proofs and refutations". http://en.wikipedia.org/wiki/Proofs_and_Refutations

-- Пн июл 25, 2011 17:09:47 --

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

Кому-то надо быть первым. Практически никто кроме меня не читал вашу статью. Из тех кто читал, положительных отзывов нет. Это единственное, что имеет значение.

Это не так. Мою статью читало много специалистов, и от некоторых из них я получил благожелательные отзывы. Посмотрите список благодарностей, я никого не благодарю впустую, а только если человек вник в статью и дал полезные конструктивные советы. Выше, например, я процитировал доказательство свойства, присланное А.Рубиным. Думаете, он не читал статью, сделав такое доказательство? R. Czerwinski в своей статье заявил, что мой рекурсивный алгоритм имеет полиномиальное время Прежде чем послать очередную версию статьи в журнал, я спрашиваю согласие на это главного редактора. Думаете, они не читают препринт, прежде чем дать такое согласие? Не все так однозначно, как Вы хотите представить. И на форуме не все так однозначны, как Вы.

-- Пн июл 25, 2011 17:17:13 --

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

Не вижу ни одного человека соглашающегося с вашей методологией.

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

-- Пн июл 25, 2011 17:27:11 --

(Оффтоп)

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

Пока что мы видим годы обсуждений и нулевой результат.

Сначала насчитали год, теперь уже годЫ. Сколько годиков насчитали? Про то, что результат уже не нулевой, я сказал выше. А вот догматическая методология в математике уже больше 30 лет с проблемой GI дает нулевой результат.

-- Пн июл 25, 2011 17:32:57 --

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

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

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

(Оффтоп)

Не первый раз Вы переписываете мои фразы как свои (с небольшими изменениями). Этот прием из детсадовской риторики выглядит крайне несолидно.