Является ли доказательство Норберта Блюма 2017 года, что правильно?

Норберт Блум недавно опубликовал 38-страничное доказательство того, что . Это правильно?$P \ne NP$

Также по теме: где еще (в интернете) обсуждается его правильность?

Примечание: фокус этого текста вопроса со временем изменился. Смотрите вопрос комментарии для деталей.

Как отмечалось здесь ранее, пример Тардоса явно опровергает доказательства; он дает монотонную функцию, которая согласуется с CLIQUE на T0 и T1, но которая лежит в P. Это было бы невозможно, если бы доказательство было правильным, поскольку доказательство применимо и к этому случаю. Однако можем ли мы точно определить ошибку? Вот из поста в блоге Липтона, что, кажется, место, где доказательство не удается:

Единственная ошибка - это одна тонкая точка в доказательстве теоремы 6, а именно на шаге 1, на странице 31 (а также 33, где обсуждается двойственный случай) - кажущееся очевидным утверждение, что содержит все соответствующие пункты, содержащиеся в т. Д., Кажется неправильным. C N F ′ ( г $C'_g$$CNF'(g)$

Чтобы объяснить это более подробно, нам нужно перейти к методу доказательства и аппроксимации Берга и Ульфберга, который повторяет первоначальное доказательство Разборовым экспоненциальной монотонной сложности для CLIQUE в терминах переключателей DNF / CNF. Вот как я это вижу:

Для каждого узла / логического элемента логической схемы (содержащей только двоичные логические элементы OR / AND) конъюнктивная нормальная форма , дизъюнктивная нормальная форма и аппроксиматоры и имеют вид прилагается. и - это просто соответствующие дизъюнктивные и конъюнктивные нормальные формы выходного сигнала. и также являются дизъюнктивными и конъюнктивными формами, но некоторых других функций «аппроксимируют» выходные данные гейта. Однако они должны иметь ограниченное количество переменных в каждом мономе дляβ C N F ( g ) D N F ( g ) C k g D r g C N F D N F D r g C k g D r g C k $g$$\beta$$CNF(g)$$DNF(g)$$C^k_g$$D^r_g$$CNF$$DNF$$D^r_g$$C^k_g$$D^r_g$(меньше константы r) и в каждом пункте для (меньше константы k).$C^k_g$

Существует понятие «ошибка», введенная в этом приближении. Как вычисляется эта ошибка? Нас интересует только некоторый набор входов T0, для которого наша общая функция принимает значение 0, и входы T1, для которых наша общая функция принимает значение 1 («обещание»). Теперь в каждом вентиле мы смотрим только на те входы от T0 и T1, которые правильно вычисляются (как и , которые представляют одну и ту же функцию - вывод гейта в ) на выходе вентиля и посмотрите, сколько ошибок / ошибок для иC N F ( g ) g β C k g D r g C k g D r g C k g C k g D r $DNF(g)$$CNF(g)$$g$$\beta$$C^k_g$$D^r_g$по сравнению с этим. Если вентиль является соединением, то выход вентиля может правильно рассчитать больше входных данных из T0 (но правильно вычисленные входные данные из T1 могут быть уменьшены). Для , который определяется как простое соединение, нет новых ошибок, однако на всех этих входах. Теперь определен как переключатель CNF / DNF для , поэтому на T0 может возникнуть ряд новых ошибок, связанных с этим переключателем. На T1 также нет новых ошибок на - каждая ошибка должна присутствовать на любом из входов гейта, и аналогично на , коммутатор не вводит новые ошибки на T1. Анализ для ИЛИ ворота является двойным.$C^k_g$$D^r_g$$C^k_g$$C^k_g$$D^r_g$

Таким образом, число ошибок для конечных аппроксиматоров ограничено числом вентилей в , умноженным на максимально возможное количество ошибок, вносимых переключателем CNF / DNF (для T0) или переключателем DNF / CNF (для T1). Но общее количество ошибок должно быть «большим», по крайней мере, в одном случае (T0 ​​или T1), поскольку это свойство положительных конъюнктивных нормальных форм с предложениями, ограниченными , что было ключевым понятием исходного доказательства Разборова (лемма 5 в статье Блюма).$\beta$$k$

Так что же сделал Блюм, чтобы справиться с отрицаниями (которые доводятся до уровня входов, поэтому схема по-прежнему содержит только двоичные вентили ИЛИ / И)?$\beta$

Его идея состоит в том, чтобы предварительно ограничить переключатели CNF / DNF и DNF / CNF, только когда все переменные положительны. Тогда коммутаторы будут работать ТОЧНО, как в случае с Бергом и Ульфбергом, с одинаковым количеством ошибок. Оказывается, это единственный случай, который необходимо рассмотреть.

Таким образом, он следует по линии Берга и Ульфберга с некоторыми отличиями. Вместо того, чтобы прикреплять , , и к каждому схемы , он присоединяет свои модификации: , , и , то есть «сокращенные» дизъюнктивные и конъюнктивные нормальные формы, которые, как он определил, отличаются от иD N F ( g ) C k g D r g g β C N F ′ ( g ) D N F ′ ( g ) C ′ k g D ′ r g C N F ( g ) D N F ( g ) C ′ r g D ′ $CNF(g)$$DNF(g)$$C^k_g$$D^r_g$$g$$\beta$$CNF'(g)$$DNF'(g)$${C'}^k_g$${D'}^r_g$$CNF(g)$$DNF(g)$«правилом поглощения», удаляющим отрицательные переменные из всех смешанных одночленов / предложений (он также использует для этой цели операцию, обозначаемую R, полностью удаляя некоторые одночлены / предложения; как мы уже обсуждали ранее, его несколько неформальное определение R на самом деле не является проблемой , R может быть точным, поэтому он применяется к каждому вентилю, но то, что удаляется, зависит не только от предыдущих двух входов, но и от всей цепи, ведущей к этому вентилю), и их аппроксиматорам и , что он также представил.${C'}^r_g$${D'}^r_g$

В теореме 5 он заключает, что для монотонной функции редуцированные и будут действительно вычислять 1 и 0 на множествах T1 и T0 в корневом узле (выход которого является выходом всей функции в ). Эта теорема, я считаю, верна. D N F ′ g 0$CNF'$$DNF'$$g_0$$\beta$

Теперь идет подсчет ошибок. Я полагаю, что ошибки в каждом узле должны быть рассчитаны путем сравнения уменьшенных и (которые теперь, возможно, две разные функции) с и как он их определил. Определения аппроксиматоров повторяют определения и (Шаг 1) при смешивании переменных с отрицательными, но когда он имеет дело с положительными переменными, он использует переключатель, как в случае с Бергом и Ульфбергом (Шаг 2). И действительно, на шаге 2 он представит такое же количество возможных ошибок, как и раньше (это тот же переключатель, и все задействованные переменные положительны).D N F ′ ( g ) C ′ r g D ′ k g C N F ′ D N F $CNF'(g)$$DNF'(g)$${C'}^r_g$${D'}^k_g$$CNF'$$DNF'$

Но доказательство неверно в Шаге 1. Я думаю, что Блум путает , , которые действительно, как он их определил, приходят от предыдущих аппроксиматоров (для ворот , ) с положительными частями и . Существует различие, и, следовательно, утверждение « прежнему содержит все предложения, содержащиеся в до аппроксимации гейта g, в котором используется выражение в или " в общем неправильно.γ 2 h 1 h 2 C N F ′ β ( h 1 ) C N F ′ β ( h 2 ) C ′ g C N F ′ β ( g ) γ ′ 1 γ ′ $\gamma_1$$\gamma_2$$h_1$$h_2$$CNF'_\beta(h_1)$$CNF'_\beta(h_2)$$C_g'$$CNF'_\beta(g)$$\gamma_1'$$\gamma_2'$

Я знаком с Александром Разборовым, чья предыдущая работа чрезвычайно важна и служит основой для доказательства Блюма. Мне посчастливилось встретиться с ним сегодня и не теряя времени, спрашивая его мнение по этому вопросу, видел ли он доказательства или нет, и что он думает об этом, если так и сделал.

К моему удивлению, он ответил, что он действительно знал о работе Блюма, но не хотел читать ее изначально. Но так как он получил больше славы, он получил возможность прочесть его и сразу обнаружил недостаток: а именно, что рассуждения, приведенные Бергом и Ульфбергом, идеально подходят для функции Тардоса, и, поскольку это так, доказательство Блюма обязательно неверно, так как противоречит ядру теоремы 6 в его статье.

Это опубликовано как ответ сообщества, потому что (а) это не мои собственные слова, а цитата из Luca Trevisan на платформе социальных сетей или от других людей, не имеющих учетной записи CSTheory.SE; и (b) каждый может свободно обновлять его соответствующей актуальной информацией.

Цитирую Лука Тревизана из публичного поста в Facebook (14.08.2017), отвечая на вопрос об этой статье, заданный Шахаром Ловеттом :

Функция Андреева, которая, как утверждается, имеет сложную суперполиномиальную схему (аннотация, затем раздел 7), является просто одномерной полиномиальной интерполяцией в конечном поле, которая, если я что-то не упускаю, разрешима путем исключения Гаусса

На самом деле, это не обязательно точка, где доказательство не удается; Затем Лука ответил на следующее (15.08.2017) после вопроса, связанного с комментарием Эндрю ниже:

Вы правы, ребята, я неправильно понял определение функции Андреева: не ясно, сводится ли она к полиномиальной интерполяции

Карл Виммер прокомментировал вопрос, поднятый Густавом Нордхом (воспроизведено с разрешения Карла):

Чтобы добавить к этому, я не понимаю, почему из первых двух параграфов доказательства теоремы 5 мы можем заключить, что вычисляет . Я вижу только некоторую односторонность, что вычисляет функцию, такую, что подразумевает, что эта функция также равна 1.$\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$$f = 1$

Третий абзац мне тоже не поможет: конечно, и его DNF / CNF-переключатель вычисляют ту же функцию, но из этого не сразу следует, что DNF / CNF-переключатель вычисляет (потому что может и не быть), поэтому мы не можем делать какие-либо выводы о -клазах.$\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$$f$

(Помимо: эта односторонность согласуется с примером Густава выше.)

С другой точки зрения, конечно, стандартная сеть, вычисляющая монотонную функцию, может вычислять немонотонные функции на внутренних узлах. Теорема 5 неприменима к немонотонным функциям, поэтому может некорректно вычислять подфункцию в сети, выходной узел которой равен (что случится для многих немонотонных функций). Из-за этого я не уверен, что эта индуктивная конструкция обязательно будет правильной в конце.$\mathrm{DNF'}(g)$$g$$\mathrm{DNF'}(g_0)$

Если я совершенно не в себе, пожалуйста, дайте мне знать!

От анонимного пользователя, в ответ на мнение Карла:

DNF 'и CNF' являются просто DNF и CNF для f, в котором выполняются сокращения противоположных литералов, что приводит к сокращению их до более короткой формы. Это также объясняется в статье, и это несколько громоздко из определения, но это то, что есть. Теорема 5 не проблема, мясо в теореме 6.

И ответ Карла (который я воспроизвожу здесь снова):

Я вижу, что говорит анон (спасибо!); мой комментарий не решал мою путаницу должным образом. Если является монотонным и вычисляется в , то можно взять , применить поглощение и оператор , а результирующий представляет собой . Используя эту «однократную» конструкцию, теорема 5 справедлива - до теоремы 6. Я замял это определение$f$$g_0$$\mathrm{DNF}(g_0)$$R$$\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$

Что я не могу понять, так это то, что конструкция «применять-поглощение-и- as-go-go- gate-by-gate» команды на страницах 27-28 делает то же самое. Кажется, что это необходимо для того, чтобы анализ по схеме «затвор-затвор» в теореме 6 работал, если только не учтена ошибка этой конструкции. Я имею в виду, не каждая функция может даже быть представлена в виде ДНФ с точки зрения с только не сведены на нет или отрицаемых литералов, но и для каждого узла , , кажется, всегда имеют эту форму. Что если в моей сети есть узел такой что не имеет такого представления?$R$$\mathrm{DNF'}(g_0)$$g$$\mathrm{DNF'}(g)$$g$$\mathrm{res}(g)$

(Еще один маленький (?) Момент: я не вижу, что делает в конструкции «Gate-by-Gate-as-you-go»; в 1.-4. Кажется, что уже является стандартной конструкцией DNF, но с поглощением и применением )$R$$\alpha$$R$

(ответ от anon) Я согласен, что неопределенность в определении R может быть проблемой в разделе 6. R не определен явно, и если только его действие не зависит каким-либо образом от всего DNF (а не от значений DNF 'на входах индуктивно) может быть проблема. Доказательство Деолаликара имело схожую проблему - два разных определения были перепутаны. Здесь, по крайней мере, мы знаем, что подразумевается под DNF ', и если это является источником проблемы в разделе 6, это можно легко отследить. Хотя я еще не заходил в раздел 6, он требует понимания доказательств аппроксиматорами Берга и Ульфберга, описанных в разделе 4, в конечном счете связанных со строительством Разборова с 1985 года, что непросто.

Объяснение того, как работает R:

Когда R применяется на каком-то шаге, он отменяет только те термины, которые, НА ЭТОМ ШАГЕ, содержат противоположные литералы (нам может потребоваться отслеживать отрицательные литералы). Например, давайте оценим как сначала, чтобы вычислить DNF 'в первом узле AND, мы получаем перед применением R , но после применения R мы теряем первый из первой скобки и получаем (где первый может иметь виртуальный NOT если бы мы его отслеживали) , Затем примените второе И, чтобы получить

$$(x\lor y) \land (\lnot x \lor y) \land (x \lor \lnot y)$$ $$((x\lor y) \land (\lnot x \lor y))\land (x \lor \lnot y)$$ $$(x\lor y) \lor ((x\land y)\lor (y\land y))$$ $x$ $$(y) \lor (x\land y)\lor (y),$$ $y$$x$ $$((y) \lor (x\land y)\lor (y)) \lor ((x\land y)\lor (x\land y) \lor (x\land y)),$$ но затем R удаляет вся первая скобка, потому что она виртуально НЕ присутствует (в этом случае нам не нужно было отслеживать предыдущие шаги, но, возможно, нам нужно вообще), оставляя или просто $$((x\land y)\lor (x\land y) \lor (x\land y))$$ $$(x\land y)$$

Правильность заявленного доказательства обсуждается в блоге Луки Тревизана: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal- нп /

В частности «Анон» разместил следующий соответствующий комментарий:

«Тардос заметил, что аргументы Разборова и Алон-Боппана переносятся на функцию, вычисляемую немонотонной схемой полиномиального размера (функция представляет собой небольшой вариант аппроксимации тэта-функции Ловаша графа). Если аргументы Берга и Ульфберга также подать заявку на функцию Тардоса (что интуитивно вероятно, поскольку их доказательство, похоже, основано на доказательстве Разборова), тогда становится ясно, что нынешнее утверждение Блюма не может быть верным. К сожалению, автор не обсуждает этот момент ».

На прямой вопрос «Михаила» ​​Александр Разборов подтверждает это (см. Пост Михаила): рассуждения, приведенные Бергом и Ульфбергом, справедливо справедливы для функции Тардоса, и, поскольку это так, доказательство Блюма обязательно неверно, поскольку оно противоречит ядру шестой теоремы в своей статье. - А. Разборов

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

Обновление (2017/08/30) Норберт Блум опубликовал следующий комментарий на своей странице arXiv:

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

Густав Нордх прокомментировал теорему 5 (стр. 29). В частности, функция

вычисляет функцию, которая равна только если и оба равны , следовательно, она является монотонной. Вышеупомянутое выражение для функции представляет собой «стандартную сеть» (где единственное отрицание относится к литералу), узлы которого соответствуют литералам и , их отрицаниям и каждому из двоичных выражений. Предположим, что выходной узел сети называется .$1$$x$$y$$1$$\beta$$x$$y$$\beta$$g_0$

Бумага Блума создает новую дизъюнктивную нормальную форму из которая выглядит как$DNF'_{\beta}(g_0)$$\beta$

Теперь, согласно теореме 5, каждый моном из является импликантом функции . Но одним из мономов в является , который не является импликантом (поскольку не влечет ), что противоречит теореме. Однако, как отмечено в комментариях , приписываемых Gustav Норд и подробное объяснение по idolvon, это очевидное несоответствие решается путем надлежащего и экспансивной интерпретации термина «происходит» в определении оператора сокращения .f D N F ′ β ( g 0 ) x f x = 1 f ( x , y ) = 1 $DNF'_{\beta}(g_0)$$f$$DNF'_{\beta}(g_0)$$x$$f$$x=1$$f(x,y)=1$$R$

Можно ли использовать списочное декодирование кодов Рида-Соломона, чтобы показать, что функция POLY Андреева находится в P, подобно тому, как Сивакумар сделал в своем сопоставимом документе членства ? Или известно, что функция POLY является NP-полной?

Он обновил свой arXiv, чтобы сказать, что его доказательство неверно:

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

Lipton и Регэна блог здесь имеет хорошую дискуссию на высоком уровне с интересным комментарием на доказательство структуры.

Они также указывают на родословную Блюма как доказательство нижней границы сложности булевой схемы, которая просуществовала более 30 лет. Это, конечно, просто «дополнительная информация», поскольку эксперты уже серьезно изучают доказательства.

Также, здесь: https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP

Цитируя Алон Амит:

(личное мнение, 14 августа, позже в тот же день): Я не думаю, что эта статья выдержит проверку. Глубокая теорема, которая была так же тщательно исследована, как и P ≠ NP, будет, по всей вероятности, решена с помощью глубоких и далеко идущих новых методов. Не исключено, что это будет решено с небольшим улучшением известных, существующих методов, но это очень, очень, очень, очень маловероятно.

Вряд ли это будет правильным по следующей причине: метод аппроксимаций является достаточно общим, чтобы с помощью них можно было доказать любую нижнюю границу. Это результат Разборова. Почему это проблема? Поскольку это означает, что метод приближений не будет основным прогрессом, он может выражать что угодно, мясо будет где-то еще. Кажется, что в статье нет такого мяса, что говорит о том, что, скорее всего, автор совершает тонкую ошибку, ту ошибку, которая скрыта от глаз, но по сути является предположением, подразумевающим ответ. Для тех, кто не является теоретиком сложности: это очень хороший тест на запах, это так же вероятно, как и чье-то заявление о создании ракеты в его подвале для поездки на Луну через неделю.

Так где же эта тонкая ошибка? В блоге Тревизана есть комментарий Ловетта о том, что это может быть скрытое предположение в теореме 6.

$NP-c$$P$

$C$$f$$f$$C$$m$

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

Некоторые (могут быть все) функции изоморфны (проблемы не являются).

$NP=P$$m$$m$$f$$f$$f$