Max Home IndustryЭто почти беспрецедентно. Во-первых, у нас есть важный результат в области информатики. Через пару месяцев он внезапно отозвался, что вызвало волну разочарования в сообществе. Но, к нашему большому облегчению, его восстановили всего через несколько дней.
Математика становится все более неряшливой? Неужели доказательствам уделяется слишком мало внимания до того, как они будут объявлены? Нет, просто среднее доказательство усложняется. Мы, вероятно, вступаем в эпоху, когда доказательства должны осесть и созреть, как хорошее вино, прежде чем мы сможем им поверить.
И да, странно использовать термин «верить», когда речь идет о чисто логическом предмете, таком как математика, но современные математические доказательства построены на столь многих других результатах, что это вопрос проверки карточного домика сверху вниз. Также существует давний вопрос, охватили ли вы все возможности. Это что-то неписаное, но хорошо известно, что любое математическое доказательство должно иметь дело со всеми способами, которыми что-то может или не может произойти, и что, если вы просто пропустили совершенно новый способ делать что-то?
Заявив о прорыве в 2016 году, Ласло Бабай опубликовал опровержение 4 января 2017 года. Теперь у нас есть сообщение, в котором утверждается, что доказательство было исправлено:
Обновление от 9 января 2017 г .: квазиполиномиальное утверждение восстановлено
4 января я объявил, что Харальд Хельфготт указал на ошибку в анализе моего теста на изоморфизм графов. Ошибка лишила законности моего предыдущего утверждения о квазиполиномиальной эффективности. Текст объявления прилагается ниже.
7 января я обнаружил замену рекурсивному вызову в подпрограмме «Split-or-Johnson», которая вызвала проблему. С этой модификацией я утверждаю, что тест на изоморфизм графа выполняется за квазиполиномиальное время (сейчас действительно).
Замена состоит из нескольких строк псевдокода, проанализированных с помощью простой новой леммы о структуре когерентных конфигураций.
Я работаю над обновленной публикацией arXiv.
Замечательно — кто бы мог подумать, что в математике есть такая драма? Ну, конечно, любой, кто хоть сколько-нибудь соприкасался с математикой!
Обновление и исходная новость следуют ниже:
Обновление изоморфизма графов 4 января 2017 г.
Это может показаться слишком драматичным, и когда вы обнаружите, что это такое, вы можете захотеть использовать термин «эзотерический», но открытие алгоритма квазиполиномиального времени для решения проблемы изоморфизма графов интересно и важно и было большой новостью еще в 2016 году. у нас есть загвоздка. Его создатель Ласло Бабай опубликовал опровержение 4 января 2017 года.
Это не лучшее начало 2017 года, но следует отдать должное Ласло Бабаю за то, что он так открыто сказал об этом. Результат был важен, см. Исходный новостной отчет, приложенный ниже, поэтому он был тщательно изучен. К сожалению, хотя в основной части статьи нет ничего плохого, во временном анализе есть изъян, который изменяет результат с квазиполиномиального времени на субэкспоненциальное.
«Техническое содержание статьи остается практически неизменным. Предыдущий анализ разбивается на один из рекурсивных шагов комбинаторной процедуры« Сплит-или-Джонсон »; но теорема« Сплит-или-Джонсон »остается в силе с обновленным временем Анализ. Все остальные результаты не затронуты. Я работаю над обновленной публикацией arXiv (с другим заголовком), которая также улучшит презентацию после комментариев нескольких коллег.
Я хочу поблагодарить Харальда Хельфготта (Геттингенский университет и CNRS) за обнаружение этой ошибки и за месяцы изучения статьи во всех деталях. Хельфготт опубликует свое описание алгоритма (с пересмотренным анализом) в серии семинаров Бурбаки ».
Результат по-прежнему впечатляет, но это не прорыв десятилетия, который в любом случае, вероятно, был громким журналистским заголовком.
Есть также основания надеяться, что доказательство может быть исправлено:
«Благодаря усилиям Харальда и его неизменному вниманию к мельчайшим деталям, я теперь уверен, что результат с пересмотренным анализом остается в силе. Более того, новые методы, представленные в статье, обеспечивают основу и инструменты для дальнейшего прогресса».
Это также отличный пример того, что современная математика настолько сложна, что доказательство не является доказательством, пока оно не простояло долгое время. Нам нравится думать, что доказательство — это последовательность проверяемых выводов, ведущих от предпосылки к теореме, но ясно, что сегодня «проверяемый» означает нечто иное, чем то, что оно значило во времена Евклида. Возможно, нам действительно нужна компьютерная помощь с нашими доказательствами.
Далее следует новость, которую я написал еще в октябре 2016 года, и ее нужно читать, оценивая волнение от нового открытия:
Ласло Бабай опубликовал отрывок из выступления, которое он представляет во вторник, 10 ноября 2015 г., в Чикаго:
Мы описываем алгоритм, который решает проблему изоморфизма графов (GI) и связанные с ней проблемы изоморфизма строк (SI) и пересечения смежных классов (CI) за квазиполиномиальное (exp (polylog n) время.
Если он действительно придумал такой алгоритм, он потребует всего информатики, поэтому требуется некоторая предыстория, чтобы объяснить это утверждение.
Сначала мы должны выяснить, в чем проблема изоморфизма графов, и это не так сложно, как кажется.
Граф — это набор узлов и дуг, которые соединяют узлы — подумайте о дорожной сети.
Проблема изоморфизма графов состоит в том, чтобы просто решить, идентичны ли два графа. Это звучит просто, но вы должны определить, какой узел соответствует узлу. Например, эти два графика выглядят по-разному, но на самом деле они одинаковы:
Предоставлено: Википедия.
Цвета дают вам соответствие между ними, которое показывает, что они идентичны или изоморфны — одинаковой формы.
Это проблема решения — изоморфны ли два графа — и это выглядит трудным. Насколько сложна проблема, можно измерить по тому, как время, необходимое для ее решения, увеличивается по мере увеличения размера проблемы.
Например, если время на решение проблемы изоморфизма графов увеличивается nc
где n — количество узлов в графе, а c — некоторая константа, тогда это полиномиальная сложность.
На первый взгляд кажется, что изоморфизм графов — гораздо более сложная проблема и, вероятно, требует экспоненциального времени в зависимости от количества узлов, то есть чего-то вроде cn
Обратите внимание, что cn становится больше любого многочлена, который вы хотите рассмотреть, например c2 c3 c4 и так далее по мере того, как n становится все больше и больше.
Хорошо, поэтому найти решение проблемы изоморфизма графов сложно, но если я дам вам решение, то есть список отображений узлов, который, как я утверждаю, является изоморфизмом, вы можете очень быстро проверить мое решение.
Проблемы со свойством, заключающимся в том, что предлагаемые решения могут быть проверены очень быстро, то есть алгоритм проверки выполняется за полиномиальное время, относятся к классу задач, называемых NP Недетерминированное полиномиальное время.
Все простые задачи, то есть те, которые могут быть решены за полиномиальное время и, следовательно, находятся в P, также находятся в NP, потому что вы, очевидно, также можете проверить решение за полиномиальное время.
Два класса сложности, P и NP, лежат в основе информатики. Один вопрос, на который мы действительно хотим ответить: P и NP разные или одинаковые. Кажется, что некоторые задачи в NP кажутся намного более сложными — это полные проблемы NP. Можно показать, что если NP-полная задача имеет полиномиальное решение, то то же самое делает каждая NP-полная задача и, следовательно, P = NP.
Если P = NP, то, вероятно, произойдут плохие вещи, потому что большая часть шифрования полагается на NP-полные проблемы, которые трудно решить, а если они находятся в P, они недостаточно сложны.
Вернемся к проблеме изоморфизма графов. Это одна из немногих хорошо известных проблем в NP, для которой не было доказано, что она находится в P или в полной NP, и после последнего результата мы все еще не знаем наверняка, но это не имеет особого значения.
Следующий вопрос, на который нам нужно ответить, — что такое квазиполиномиальное время. Другой способ записать полиномиальное время:
nc = ec (loge n)
что, как вы видите, верно, потому что loge n — это то, на что вам нужно поднять e, чтобы получить n.
Квазиполиномиальное время:
ec (loge n) ^ k
для некоторого k, что сводится к полиномиальному времени при k = 1. Если k больше 1, то время растет быстрее, чем любой алгоритм с полиномиальным временем, но намного меньше, чем алгоритм с экспоненциальным временем.
Итак, результат, который мы имеем, если предположить, что доказательство Бабая подтверждено, состоит в том, что проблема в NP, которая не была доказана как NP-полная, имеет алгоритм квазиполиномиального времени. Дело в том, что это время настолько близко к полиномиальному, что не имеет большого значения.
Так что это значит для NP = P?
Это означает, что пример проблемы NP, которая на первый взгляд кажется экспоненциально сложной, не является. В прошлом были и другие примеры этого — доказательство того, что число является простым или нет, считалось в EXP, но недавно был обнаружен алгоритм, который был в P.
Может ли быть, что другие проблемы NP, которые, кажется, находятся в EXP, являются квазиполиномиальными? Может ли быть, что полная проблема NP, такая как факторинг, может быть квазиполиномиальной?
Вы можете возразить, что если бы полные проблемы NP были квазиполиномиальными, то NP все равно не было бы P, но с точки зрения практических аспектов, таких как шифрование, они были бы практически равны. Вы могли бы сказать, что вам не нужно доказывать NP = P, доказывая, что NP = QP достаточно.
Что удивительно, так это потрясающие теоретические инструменты, которые кажутся необходимыми для доказательства такого рода результатов. Предполагается, что доказательство опирается на классификацию простых групп. Действительно ли нужны такие продвинутые методы для поиска эффективных алгоритмов?
Наверное.