Была ли решена проблема изоморфизма графов?

13

Страница проблемы изоморфизма графов Википедии, похоже, указывает на то, что нет, она не была решена. Однако мой друг указал на Алгоритм Полиномиального Времени для Изоморфизма Графов . Я недостаточно опытен, чтобы следовать рассуждениям в газете.

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

Итак, решена ли проблема изоморфизма графов?

Тайлер Спаэт
источник
1
стоящий вопрос. В отношении кибер-экспертной оценки было бы лучше, если бы респонденты / ответы на самом деле указывали на конкретную ошибку (ы) в документе, а не на общие черты. по общему признанию, однако, вот то, что профессиональные ученые думают об этих типах усилий. arxiv полон ошибочных статей, многие из которых посвящены P против NP, но многие другие полусмертные проблемы привлекают любительские усилия, например, гипотеза Коллатца, двойные простые числа, гипотеза Гольдбаха и т. д.
vzn
7
@vzn Не думаю, что есть смысл тратить наше время на чтение статей, которые почти наверняка неверны и не проливают новый свет на проблему.
Юваль Фильмус
2
@vzn Я не понимаю твою жалобу. Ответ DW (опубликованный за час до вашего комментария) содержит ссылку на комментарий, который указывает на конкретную ошибку в обсуждаемой статье ArXiv.
Дэвид Ричерби
2
@vzn Статья ArXiv содержит ошибку. Он не был исправлен, чтобы исправить эту ошибку. Больше нет необходимости в рецензировании. Я понятия не имею, что вы говорите из вторых рук: контр-пример является контр-примером, независимо от того, был ли он сообщен вам его первооткрывателем или торговцем наркотиками, который тусуется за этим отвратительным баром на шоссе.
Дэвид Ричерби
1
@vzn Предположительно, он не был исправлен, потому что автор не смог исправить ошибку. Обратите внимание, что ArXiv не разрешает отзыв рукописей, даже если они оказываются неверными.
Дэвид Ричерби

Ответы:

23

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

Как объясняет Юваль, нередки случаи, когда любители пытаются решить эти проблемы; они имеют тенденцию быть испорченными. Когда дело доходит до результатов по известным открытым проблемам (например, P против NP, изоморфизм графов и т. Д.), Я рекомендую искать опубликованную литературу в авторитетных рецензируемых конференциях и журналах - рецензирование не является идеальным, но рецензируемые статьи имеют гораздо более высокую вероятность быть правильным.

DW
источник
17

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

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

Юваль Фильмус
источник
2
Еще один способ справиться с подобными претензиями экспертов - невозможность или барьерные результаты. затем более информативное опровержение выражается в виде «в статье используется тип аргумента [x] для решения проблемы изоморфизма, но из исследований [a, b, c] известно, что для этого типа существует определенный барьер»). подхода, и газета, похоже, не знает об этом барьере или конкретно показывает, как его преодолеть ". об этом известны результаты для проблемы изоморфизма и других ключевых проблем, например, P vs NP.
августа
1
Попытка решить нерешенные проблемы, подобные этой (и неуспешной ...), может быть очень плодотворным процессом обучения, если у вас будет правильное мышление.
Ник Алджер
тем не менее, некоторые споры : доказательства / претензии имеют в какой-то степени обоснованность, не зависящую от «принятия более широким научным сообществом» и знания о них отдельными лицами. например, когда правильное доказательство впервые вводится, оно не сразу / мгновенно «принимается» кем-либо, кроме автора. дальнейшую поддержку этой динамики можно найти в истории математики. И иногда длительные периоды могут идти между введением претензий / утверждений и принятием, например , в случае Галуа, Ramanujan и т.д.
ВЗН
8

Я был бы очень сомнителен, что это имеет (в смысле доказательства существования алгоритма полиномиального времени). Хотя не исключено, что бумага правильная, существует ряд предупреждающих знаков:

  1. Автор не опубликовал результат в рецензируемом месте (даже после 7 лет).
  2. Автор, похоже, нигде больше не публиковал.
  3. В статье представлены алгоритмы, но утверждение о корректности является неформальным аргументом о сложности.
  4. Для задачи, которая противостояла попыткам некоторых очень умных людей, математика в статье слишком проста.
  5. Автор не связан с академическим учреждением. Новая версия статьи проясняет это.

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

Чтобы уточнить (4) с учетом последних новостей, Ласло Бабай недавно заявил , значительное улучшение по известному алгоритму изоморфизма графов (не препринт еще, но приличный ход комментарий на своей публичной лекции можно найти здесь ), что дает алгоритм времени псевдо-многочленом. Бабай и его коллеги, безусловно, очень умные люди, и математика, используемая для получения этого результата, сложна, глубока и охватывает теорию графов и теорию групп. Учитывая вес вероятности, это ожидаемый уровень для значительного продвижения по такой проблеме, как эта.

Люк Мэтисон
источник
3
Точки 1-4 сильны, но 5 гораздо более косвенные.
Дэвид Ричерби
(5) не правильно. Учреждение (по-видимому) является Техническим университетом Берлина и частично финансируется государством. (1) поддерживается этой ссылкой / гусеничном шасси. статья цитируется на странице претензий Woeginger .
vzn
3

Ласло Бабай заявил, что нашел решение квазиполиномиальной задачи об изоморфизме графов по состоянию на 11 ноября 2015 года.

... и отозвал претензию вчера (01.04.2017):

Источник: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

bharv14
источник
По предоставленной вами ссылке: Бабаи еще не выпустил препринт, и когда я спросил его, он сказал «скоро, скоро». До тех пор.
Scaaahu
Вопрос не определяет, что будет означать, что проблема изоморфизма графов будет считаться решенной, но наиболее вероятная интерпретация состоит в том, что кто-то нашел для нее алгоритм за полиномиальное время или дал свидетельство того, что такого алгоритма за полиномиальное время не существует. , Согласно этой интерпретации, этот ответ не отвечает на вопрос.
DW