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

232

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

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

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

Уоррен Шуди
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Бьёрн Кьос-Хансен

Ответы:

98

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

Единственная ошибка - это одна тонкая точка в доказательстве теоремы 6, а именно на шаге 1, на странице 31 (а также 33, где обсуждается двойственный случай) - кажущееся очевидным утверждение, что содержит все соответствующие пункты, содержащиеся в т. Д., Кажется неправильным. C N F ( г )CgCNF(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 ggβCNF(g)DNF(g)CgkDgrCNFDNFDgrCgkDgr(меньше константы r) и в каждом пункте для (меньше константы k).Cgk

Существует понятие «ошибка», введенная в этом приближении. Как вычисляется эта ошибка? Нас интересует только некоторый набор входов 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 gDNF(g)CNF(g)gβCgkDgrпо сравнению с этим. Если вентиль является соединением, то выход вентиля может правильно рассчитать больше входных данных из T0 (но правильно вычисленные входные данные из T1 могут быть уменьшены). Для , который определяется как простое соединение, нет новых ошибок, однако на всех этих входах. Теперь определен как переключатель CNF / DNF для , поэтому на T0 может возникнуть ряд новых ошибок, связанных с этим переключателем. На T1 также нет новых ошибок на - каждая ошибка должна присутствовать на любом из входов гейта, и аналогично на , коммутатор не вводит новые ошибки на T1. Анализ для ИЛИ ворота является двойным.CgkDgrCgkCgkDgr

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

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

Его идея состоит в том, чтобы предварительно ограничить переключатели 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 rCNF(g)DNF(g)CgkDgrgβCNF(g)DNF(g)CgkDgrCNF(g)DNF(g)«правилом поглощения», удаляющим отрицательные переменные из всех смешанных одночленов / предложений (он также использует для этой цели операцию, обозначаемую R, полностью удаляя некоторые одночлены / предложения; как мы уже обсуждали ранее, его несколько неформальное определение R на самом деле не является проблемой , R может быть точным, поэтому он применяется к каждому вентилю, но то, что удаляется, зависит не только от предыдущих двух входов, но и от всей цепи, ведущей к этому вентилю), и их аппроксиматорам и , что он также представил.CgrDgr

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

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

Но доказательство неверно в Шаге 1. Я думаю, что Блум путает , , которые действительно, как он их определил, приходят от предыдущих аппроксиматоров (для ворот , ) с положительными частями и . Существует различие, и, следовательно, утверждение « прежнему содержит все предложения, содержащиеся в до аппроксимации гейта g, в котором используется выражение в или " в общем неправильно.γ 2 h 1 h 2 C N F β ( h 1 ) C N F β ( h 2 ) C g C N F β ( g ) γ 1 γ 2γ1γ2h1h2CNFβ(h1)CNFβ(h2)CgCNFβ(g)γ1γ2

idolvon
источник
2
кажется, тот же комментарий в блоге RJL rjlipton.wordpress.com/2017/08/17/… ты это написал? хотел бы добавить идею: что, если ключом является рассмотрение T0 / T1 всех равных 1-бит по отношению к преобразованию / приближению cnf-dnf? Берковицу, 1982, известно, что этого достаточно, чтобы отделить P от NP, см. «сложность функций срезов» / wegener sciencedirect.com/science/article/pii/0304397585902099
vzn
6
@vzn Автор этого комментария в блоге - "vloodin". Автор этого ответа "идолвон". Перестановка букв дает подсказку, авторы не слишком отличаются.
Клемент С.
2
Просто любопытно, было ли какое-либо дальнейшее публичное общение с Блюмом после загрузки газеты в архив?
Мэтт
9
@Matt Blum отозвал газету и разместил следующий комментарий на странице arXiv: «Доказательство неверно. Я уточню, в чем именно заключается ошибка. Для этого мне понадобится некоторое время. Я объясню свое домашняя страница "
Gustav Nordh
Этот ответ был подтвержден как правильный Скотт Ааронсон, ссылаясь на других (неназванных) рецензентов: scottaaronson.com/blog/?p=3409
cuniculus
95

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

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

Михаил
источник
2
Было бы здорово, если бы вы могли уточнить это. Известно ли, что функция Тардоса находится в P?
Томас
5
Функция Тардоса находится в P и является приближением тета-функции Ловаша, которая для дополнения графа находится между числом клики и хроматическим числом. Тета-функция Ловаша - это монотонная функция графа. Однако вопрос в том, является ли это приближение причиной монотонной функции графа (только монотонная функция сделает недействительным доказательство). Может кто-нибудь дать нам ссылку на газету Тардос, где это определено, пожалуйста?
идолвон
7
@idolvon Вы имеете в виду это: cs.cornell.edu/~eva/… В нем прямо говорится, что функция φ является монотонной функцией,
вычисляемой по многим временам
12
Спасибо! Это в основном решает проблему - доказательство Блума должно быть неверным. Теперь, возможно, было бы интересно определить ошибку. Я посмотрю на это и опубликую комментарий к lipton's, как в старые добрые времена, согласно проф. p пожелания дятла
кумир
1
@idolvon Да, я тоже так думал. Аргументы Блума должны нести функцию φ, как определено в этой статье, в которой говорится, что она монотонна и вычисляется многократно (тривиально по определению).
PsySp
41

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


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

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

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

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


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

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

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

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

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

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


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

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


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

Я вижу, что говорит анон (спасибо!); мой комментарий не решал мою путаницу должным образом. Если является монотонным и вычисляется в , то можно взять , применить поглощение и оператор , а результирующий представляет собой . Используя эту «однократную» конструкцию, теорема 5 справедлива - до теоремы 6. Я замял это определениеfg0DNF(g0)RDNF(g0)fDNF(g0)

Что я не могу понять, так это то, что конструкция «применять-поглощение-и- as-go-go- gate-by-gate» команды на страницах 27-28 делает то же самое. Кажется, что это необходимо для того, чтобы анализ по схеме «затвор-затвор» в теореме 6 работал, если только не учтена ошибка этой конструкции. Я имею в виду, не каждая функция может даже быть представлена в виде ДНФ с точки зрения с только не сведены на нет или отрицаемых литералов, но и для каждого узла , , кажется, всегда имеют эту форму. Что если в моей сети есть узел такой что не имеет такого представления?RDNF(g0)gDNF(g)gres(g)

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


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

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

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

(xy)(¬xy)(x¬y)
((xy)(¬xy))(x¬y)
(xy)((xy)(yy))
x
(y)(xy)(y),
yx
((y)(xy)(y))((xy)(xy)(xy)),
но затем R удаляет вся первая скобка, потому что она виртуально НЕ присутствует (в этом случае нам не нужно было отслеживать предыдущие шаги, но, возможно, нам нужно вообще), оставляя или просто
((xy)(xy)(xy))
(xy)
Clement C.
источник
6
Я скептически отношусь к этому (но не использую Facebook, чтобы что-то там говорить) - функция Андреева (в статье) дается в виде двудольного графа с наборами левой и правой вершин, равными GF (q), плюс произвольный набор ребер и степень связана. Вопрос в том, существует ли способ выбрать для каждой вершины слева одного из ее соседей, чтобы индуцированная функция (слева направо) была полиномом низкой степени. Комментарий Луки применяется, как только у нас есть хороший выбор соседа для каждой левой вершины (поскольку тогда это просто полиномиальная интерполяция), но мне не ясно, как сделать правильный выбор.
Эндрю Морган
@AndrewMorgan Я обновил ответ CW.
Клемент С.
@ Карл Виммер: относительно погоды DNF ′ (g0) вычисляет f, нужно использовать, что f монотонно, я думаю. В теореме 5 предполагается, что f монотонна.
кумир
смущенный! это все цитаты из поста в фейсбуке? при нажатии на ссылку shachar lovett на facebook выше, некоторые из приведенных выше ответов видны мне, а другие не видны для меня. например, Карл Виммер. это связано с тем, что некоторые друзья проверяют отклики в Facebook? если это так, то это разочаровывает, и это не очень хорошее место для публичного обсуждения. может кто-нибудь может сделать скриншот? :( или вы цитируете материал вне поста в фейсбуке? Пожалуйста, будьте осторожны / дополните цитатами / URL-адресами
vzn
ой! В дальнейшем исследовании вы также цитируете ответы из поста в блоге baez, который содержит ответ Wimmers и
vzn
36

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

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

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

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

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

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

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

Густав Норд
источник
3
Я отправил это как ответ, поскольку у меня еще нет привилегий оставлять комментарии.
Густав Норд
11
Да, это мое понимание (но я могу ошибаться). Функция Тардоса - это монотонная функция, которая равна 1 на k-клике и 0 на полных (k-1) -раздельных графах. Насколько я могу судить, Берг и Ульфберг используют ТОЛЬКО эти свойства в своем доказательстве приближения CNF-DNF для CLIQUE, что, следовательно, доказывает, что функция Тардоса имеет экспоненциальную монотонную сложность. Теорема Блюма 6 гласит, что нижние оценки монотонной сложности в приближении CNF-DNF для монотонных функций дают ту же НЕ-монотонную нижнюю оценку. Следовательно, функция Тардоса имеет экспоненциальную сложность согласно теореме 6 (что неверно).
Густав Норд,
5
В этом случае, похоже, что решение этого вопроса должно быть основным направлением сейчас ... Я не верю, что я достаточно компетентен или достаточно осведомлен, чтобы это сделать, но (скрещенные пальцы, которые не помогают печатать) другие.
Клемент С.
3
Где определена эта функция Tardos, может кто-нибудь дать ссылку на статью? Ясно, что существуют немонотонные функции, которые разделяют T0 и T1, которые находятся в P (легко построить, скажем, проверку, если у нас есть полный граф с k узлами), но является ли функция Tardos монотонной? Если монотонно, и разделяет T0 и T1, это сделает недействительным доказательство. Но если это не монотонно, то доказательство может быть верным.
идолвон
4
Функция Тардос определена в ее очень короткой статье, расположенной здесь: cs.cornell.edu/~eva/… Более того, свойства функции Тардос подробно обсуждаются в [S. Юкна, Сложность булевой функции с. 272]
Густав Норд
25

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

(xy)(¬xy)(x¬y)

вычисляет функцию, которая равна только если и оба равны , следовательно, она является монотонной. Вышеупомянутое выражение для функции представляет собой «стандартную сеть» (где единственное отрицание относится к литералу), узлы которого соответствуют литералам и , их отрицаниям и каждому из двоичных выражений. Предположим, что выходной узел сети называется .1xy1βxyβg0

Бумага Блума создает новую дизъюнктивную нормальную форму из которая выглядит какDNFβ(g0)β

xy(xy)

Теперь, согласно теореме 5, каждый моном из является импликантом функции . Но одним из мономов в является , который не является импликантом (поскольку не влечет ), что противоречит теореме. Однако, как отмечено в комментариях , приписываемых Gustav Норд и подробное объяснение по idolvon, это очевидное несоответствие решается путем надлежащего и экспансивной интерпретации термина «происходит» в определении оператора сокращения .f D N F β ( g 0 ) x f x = 1 f ( x , y ) = 1 RDNFβ(g0)fDNFβ(g0)xfx=1f(x,y)=1R

kdog
источник
2
Похоже, что DNF 'для этой формулы: (x AND y) - сформируйте полное DNF, отмените тривиальные термины и примените поглощение
idolvon
2
@idolvon Вы правильно используете альтернативное определение на стр. 29. Но основное определение приведено на стр. 27-28, и по этому определению первоначальный анализ Нордха является правильным. Я не собираюсь прыгать вокруг бумаги и пытаться догадаться, что задумал автор, особенно когда текст определения на страницах 27-28 очень ясен в этом случае. Кроме того, другие доказательства в статье используют определение на стр. 27-28, а не «альтернативное определение» на странице 29.DNF
kdog
2
Определение на страницах 27-28 включает использование оператора R, который не определен, за исключением расплывчатой ​​фразы «происходит из тривиального монома». Если мы примем это в значении «будет отменено, если литералы будут поддерживаться до этой стадии», то определения будут одинаковыми. В любом случае вам потребуется НЕКОТОРЫЕ толкования для R. Так как R так важен в главе 6, правильная интерпретация важна, и на самом деле есть та, которая является индуктивной.
идолвон
2
(xy)(¬xy)(x¬y)
((xy)(¬xy))(x¬y)
(xy)((xy)(yy))
x
(y)(xy)(y),
2
yx
((y)(xy)(y))((xy)(xy)(xy)),
((xy)(xy)(xy))
(xy)
17

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

Лэнс Фортноу
источник
10
Ланс, я не отвечаю на твои вопросы. В июне 1986 года Дэвид Джонсон в «Открытой проблеме месяца» спросил, является ли проблема Андреева NP-полной. См. Колонку Давида NP-полноты в Журнале Алгоритмов 7: 2, с. 289-305. Не уверен, было ли когда-нибудь решение.
Рави Боппана
1
Статья Джонсона 1986 года предшествует методам полиномиальной реконструкции и результатам декодирования списков 90-х годов.
Лэнс Фортноу
1
Вот моя идея, используя обозначения в Разделе 7 статьи Норберта Блюма. Полином p, который является решением проблемы POLY, можно рассматривать как кодовое слово Рида-Соломона. Выберите функцию f, выбрав случайным образом ребро из каждой вершины в A. Это f должно совпадать с p в значительно более чем 1 / q доле входных данных. Затем мы можем использовать декодирование списка для f, чтобы создать полиномиально длинный список возможностей для p, и мы можем проверить каждую из них.
Лэнс Фортноу
1
qddpdqlogq1q
4
@ Matt Предполагая, что я правильно прочитал вышеизложенное, эта функция - та, которую Блум утверждает, что доказала сложность суперполиномиальной схемы. Но если он находится в P, он должен иметь сложность полиномиальной схемы, противоречащую предполагаемому доказательству P против NP.
Климент С.
14

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

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

Mehrdad
источник
9

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

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

kodlu
источник
3

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

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

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

Джек
источник
11
Это не аргумент (действительное мнение, и я признаю, что разделяю его, но не действительный аргумент, который, как я полагаю, мы должны иметь здесь). Такого рода вещи случались раньше .
Клемент С.
8
Да я ничего не спорил. Просто ответьте на вопрос «где обсуждается этот документ», а затем подведите итоги обсуждения до этого момента.
Джек,
2

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

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

скептик
источник
хороший / актуальный момент; fyi razborovs "не ходи", то есть "по методу приближений" (1989) people.cs.uchicago.edu/~razborov/files/approx.pdf, но чувствую, что это доказательство не очень хорошо проанализировано. Нужно тщательно понимать, выходят ли его установленные условия за пределы слов «метод аппроксимаций», который прошел через доработки / разработки / уточнения и т. д. с момента его создания Разборовым. эти точные условия, по-видимому, не слишком анализируются более поздними исследователями. Другой серьезный барьер - естественные доказательства Разборов / Рудич. en.wikipedia.org/wiki/Natural_proof
vzn
отрицательно, потому что содержание этого ответа уже были рассмотрены в предыдущих ответах.
проверка
-2

NPcP

CffCm

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

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

NP=Pmmfff

Ixer
источник