A prova de 2017 de Norbert Blum de que

Norbert Blum postou recentemente uma prova de 38 páginas de que . Está correto?$P \ne NP$

Também no tópico: onde mais (na internet) sua correção está sendo discutida?

Nota: o foco deste texto da pergunta mudou com o tempo. Veja os comentários da pergunta para obter detalhes.

Como observado aqui antes, o exemplo de Tardos refuta claramente a prova; fornece uma função monótona, que concorda com CLIQUE em T0 e T1, mas está em P. Isso não seria possível se a prova estivesse correta, pois a prova também se aplica a esse caso. No entanto, podemos identificar o erro? Aqui está, em uma postagem no blog do lipton, o que parece ser o lugar onde a prova falha:

O erro único é um ponto sutil na prova do Teorema 6, ou seja, na Etapa 1, na página 31 (e também 33, onde o caso duplo é discutido) - uma alegação aparentemente óbvia de que contém todas as cláusulas correspondentes contidas em etc, parece errado. C N F ′ ( g $C'_g$$CNF'(g)$

Para explicar isso com mais detalhes, precisamos entrar no método de prova e aproximação de Berg e Ulfberg, que reafirma a prova original de Razborov da complexidade exponencial de monótonos para CLIQUE em termos de comutadores DNF / CNF. É assim que eu vejo:

Para cada nó / porta de um circuito lógico (contendo apenas portas binárias OR / AND), uma forma normal conjuntiva , uma forma normal disjuntiva e aproximadores e são em anexo. e são simplesmente as formas normais disjuntivas e conjuntivas correspondentes da saída do gate. e também são formas disjuntivas e conjuntivas, mas de algumas outras funções, "aproximando" a saída do portão. No entanto, eles precisam ter um número limitado de variáveis ​​em cada monômio paraβ 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$(menor que uma constante r) e em cada cláusula para (menor que uma constante k).$C^k_g$

Existe a noção de um "erro" introduzido com esta aproximação. Como esse erro é calculado? Estamos interessados ​​apenas em algum conjunto T0 de entradas nas quais nossa função total assume o valor 0 e T1 em entradas nas quais nossa função total assume o valor 1 (uma "promessa"). Agora, em cada porta, examinamos apenas as entradas de T0 e T1, que são computadas corretamente (por e , que representam a mesma função - saída da porta em ) na saída da porta , e veja quantos erros / erros existem para eC 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$, comparado a isso. Se o gate for uma conjunção, a saída do gate poderá calcular mais entradas de T0 corretamente (mas as entradas calculadas corretamente de T1 possivelmente diminuirão). Para , que é definido como uma conjunção simples, no entanto, não há novos erros em todas essas entradas. Agora, é definido como um comutador CNF / DNF de , portanto, pode haver vários erros novos em T0, provenientes desse comutador. Também em T1 não há novos erros em - cada erro deve estar presente em qualquer uma das entradas de porta e, da mesma forma em , o switch não introduz novos erros em T1. A análise para o portão OR é dupla.$C^k_g$$D^r_g$$C^k_g$$C^k_g$$D^r_g$

Portanto, o número de erros para os aproximadores finais é limitado pelo número de portas em , vezes o número máximo possível de erros introduzidos por um comutador CNF / DNF (para T0) ou por um comutador DNF / CNF (para T1). Mas o número total de erros deve ser "grande" em pelo menos um caso (T0 ou T1), já que essa é uma propriedade de formas normais conjuntivas positivas com cláusulas delimitadas por , que foi o principal insight da prova original de Razborov (Lemma 5 no artigo de Blum).$\beta$$k$

Então, o que Blum fez para lidar com negações (que são empurradas para o nível de entradas, para que o circuito ainda contenha apenas portas binárias OR / AND)?$\beta$

Sua idéia é pré-formatar os comutadores CNF / DNF e DNF / CNF de forma restritiva, somente quando todas as variáveis ​​forem positivas. Em seguida, os comutadores funcionariam exatamente como no caso de Berg e Ulfberg, introduzindo a mesma quantidade de erros. Acontece que este é o único caso que precisa ser considerado.

Então, ele segue as linhas de Berg e Ulfberg, com algumas distinções. Em vez de anexar , , e a cada porta do circuito , ele anexa suas modificações, , , e , ou seja, as formas normais disjuntivas e conjuntivas "reduzidas", que ele definiu como diferentes das eD 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)$por "regra de absorção", removendo variáveis ​​negadas de todos os monômios / cláusulas mistas (ele também usa para esse propósito a operação indicada por R, removendo totalmente alguns monômios / cláusulas; como discutimos anteriormente, sua definição um tanto informal de R não é realmente o problema , R pode ser tornado preciso para que seja aplicado em cada porta, mas o que é removido depende não apenas das duas entradas anteriores, mas de todo o circuito que antecede essa porta) e de seus aproximadores e , que ele também apresentou.${C'}^r_g$${D'}^r_g$

Ele conclui, no Teorema 5, que para uma função monótona, e reduzidos realmente computarão 1 e 0 nos conjuntos T1 e T0, no nó raiz (cuja saída é a saída de toda a função em ). Acredito que esse teorema esteja correto. D N F ′ g 0$CNF'$$DNF'$$g_0$$\beta$

Agora vem a contagem de erros. Eu acredito que os erros em cada nó devem ser calculados comparando e (que agora são possivelmente duas funções diferentes), com e como ele os definiu. As definições de aproximação aproximam as definições de e (Etapa 1) ao misturar variáveis ​​com negadas, mas quando ele lida com variáveis ​​positivas, ele usa a opção como no caso de Berg e Ulfberg (Etapa 2). E, de fato, na Etapa 2, ele apresentará o mesmo número de erros possíveis como antes (é a mesma opção e todas as variáveis ​​envolvidas são positivas).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'$

Mas a prova está errada na Etapa 1. Acho que Blum está confundindo , , que realmente vem, como ele os definiu, de aproximadores anteriores (para portões , ), com partes positivas da e . Existe uma diferença e, portanto, a instrução " ainda contém todas as cláusulas contidas no antes da aproximação do gate g que usa uma cláusula em ou " parece ser errado em geral.γ 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'$

Conheço Alexander Razborov, cujo trabalho anterior é extremamente crucial e serve de base para a prova de Blum. Tive a sorte de encontrá-lo hoje e não perdi tempo em pedir sua opinião sobre todo esse assunto, se ele tinha visto a prova ou não e quais são seus pensamentos sobre isso, se o fizesse.

Para minha surpresa, ele respondeu que realmente conhecia o artigo de Blum, mas não se importou em lê-lo inicialmente. Mas quanto mais fama foi dada a ele, ele teve a chance de lê-lo e detectou uma falha imediatamente: a saber, que os raciocínios dados por Berg e Ulfberg se mantêm perfeitamente para a função de Tardos e, como é o caso, a prova de Blum é necessariamente incorreto, pois contradiz o núcleo do Teorema 6 em seu artigo.

Isso é publicado como resposta da comunidade porque (a) não são minhas próprias palavras, mas uma citação de Luca Trevisan em uma plataforma de mídia social ou de outras pessoas sem conta no CSTheory.SE; e (b) qualquer pessoa deve se sentir à vontade para atualizar isso com informações relevantes e atualizadas.

Citando Luca Trevisan de uma publicação pública no Facebook (14/08/2017), respondendo a uma pergunta sobre este artigo feita por Shachar Lovett :

A função de Andreev, que é reivindicada como tendo uma complexidade de circuito superpolinomial (abstrata, seção 7), é apenas uma interpolação polinomial univariada em um campo finito que, se não estou faltando alguma coisa, é solucionável pela eliminação gaussiana

Na verdade, esse não é necessariamente um ponto em que a prova falha; Luca respondeu então (15/08/2017), após uma pergunta relacionada ao comentário de Andrew abaixo:

Você está certo, pessoal, eu entendi mal a definição da função de Andreev: não está claro que isso se reduz à interpolação polinomial

Karl Wimmer comentou o ponto levantado por Gustav Nordh (reproduzido com a permissão de Karl):

$\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$$f = 1$

$\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$$f$

(Além disso: esse lado unilateral é consistente com o exemplo de Gustav acima.)

$\mathrm{DNF'}(g)$$g$$\mathrm{DNF'}(g_0)$

Se eu estiver totalmente fora da base aqui, por favor me avise!

De um usuário anônimo, em reação ao argumento de Karl:

DNF 'e CNF' são apenas DNF e CNF para f, nos quais são feitos cancelamentos de literais opostos, reduzindo-os para uma forma mais curta. Isso também é explicado no artigo e é um tanto complicado com a definição, mas é isso que é. Teorema 5 não é o problema, a carne está no Teorema 6.

E a resposta de Karl (que reproduzo novamente aqui):

$f$$g_0$$\mathrm{DNF}(g_0)$$R$$\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$

$R$$\mathrm{DNF'}(g_0)$$g$$\mathrm{DNF'}(g)$$g$$\mathrm{res}(g)$

$R$$\alpha$$R$

(resposta de anon) Concordo que a indefinição na definição de R pode ser um problema na seção 6. R não está definido explicitamente, e a menos que sua ação dependa de alguma forma em todo o DNF (e não nos valores de DNF 'nos portões indutivamente) , pode haver um problema. A prova de Deolalikar teve um problema semelhante - duas definições diferentes foram confusas. Aqui, pelo menos, sabemos o que se entende por DNF 'e, se isso é fonte do problema na seção 6, pode ser fácil rastrear. Ainda não entrei na seção 6, porém, requer a compreensão de provas dos aproximadores de Berg e Ulfberg, descritas na seção 4, relacionadas à construção de Razborov em 1985, o que não é fácil.

Explicação como R funciona:

$$(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)),$$ $$((x\land y)\lor (x\land y) \lor (x\land y))$$ $$(x\land y)$$

A correção da prova reivindicada está sendo discutida no blog de Luca Trevisan: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal- np /

Em particular, "anon" postou o seguinte comentário relevante:

"Tardos observou que os argumentos de Razborov e Alon-Boppana são transferidos para uma função que é calculada por um circuito não monótono de tamanho polinomial (a função é uma pequena variante na aproximação da função teta de Lovasz do gráfico). Se os argumentos de Berg e Ulfberg também Se você solicitar a função de Tardos (que é intuitivamente provável, pois a prova parece basear-se na prova de Razborov), fica claro que a alegação atual de Blum não pode estar correta. Infelizmente, o autor não discute esse ponto ".

Em uma pergunta direta de "Mikhail", Alexander Razborov confirma isso (veja o post de Mikhail): os raciocínios de Berg e Ulfberg são perfeitamente válidos para a função de Tardos, e, como é o caso, a prova de Blum é necessariamente incorreta, pois contradiz o núcleo. do sexto teorema em seu artigo. - A. Razborov

Na minha opinião, isso definitivamente resolve a questão de saber se o artigo está correto ou não (NÃO está correto!). Também é importante observar que parece difícil reparar a prova, pois o próprio método de prova parece falho.

Atualização (30/08/2017) Norbert Blum postou o seguinte comentário em sua página do arXiv:

A prova está errada. Vou elaborar precisamente qual é o erro. Para fazer isso, preciso de um tempo. Vou colocar a explicação na minha página inicial

Gustav Nordh comentado pelo Teorema 5 (página 29). Especificamente, a função

$1$$x$$y$$1$$\beta$$x$$y$$\beta$$g_0$

$DNF'_{\beta}(g_0)$$\beta$

$DNF'_{\beta}(g_0)$$f$$DNF'_{\beta}(g_0)$$x$$f$$x=1$$f(x,y)=1$$R$

Alguém poderia usar a decodificação de lista de códigos de Reed-Solomon para mostrar que a função POLY de Andreev está em P, semelhante à maneira que Sivakumar fez em seu artigo comparável de membro ? Ou a função POLY é conhecida por ser NP-completa?

Ele atualizou seu arXiv para dizer que sua prova está incorreta:

A prova está errada. Vou elaborar precisamente qual é o erro. Para fazer isso, preciso de um tempo. Vou colocar a explicação na minha página inicial.

O blog de Lipton e Regan aqui tem uma boa discussão de alto nível com um comentário interessante sobre a estrutura de provas.

Eles também apontam o pedigree de Blum como tendo demonstrado um limite mais baixo na complexidade do circuito booleano que durou mais de 30 anos. É claro que isso é apenas "informação secundária", já que os especialistas já estão estudando seriamente a prova.

Além disso, aqui: https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP

Citando Alon Amit:

(opinião pessoal, 14 de agosto, mais tarde): Não creio que este artigo seja submetido a escrutínio. Um teorema profundo, que foi tão pesquisado em massa quanto P ≠ NP, provavelmente será resolvido com novas técnicas profundas e de longo alcance. Não é impossível que ele seja resolvido com um ligeiro aprimoramento dos métodos conhecidos e existentes, mas é muito, muito, muito improvável.

É improvável que esteja correto pelo seguinte motivo: o método de aproximações é geral o suficiente para que qualquer limite inferior possa ser comprovado usando-os. Este é um resultado devido a Razborov. Por que isso é um problema? Como significa que o método de aproximações não será o principal progresso, ele pode expressar qualquer coisa, a carne estará em outro lugar. Parece não haver tanta carne no artigo, o que sugere que o autor provavelmente está cometendo um erro sutil, o tipo de erro oculto aos olhos, mas essencialmente uma suposição que implica a resposta. Para aqueles que não são teóricos da complexidade: este é um teste de cheiro muito bom, é tão provável que seja verdade quanto a afirmação de alguém de construir um foguete em seu porão para viajar para a lua em uma semana.

Então, onde está esse erro sutil? No blog de Trevisan, há um comentário de Lovett sugerindo o que essa suposição oculta pode estar no teorema 6.

$NP-c$$P$

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

Uma função booleana possui apenas uma tabela de verdade, mas não uma única expressão algébrica, nem um problema possui apenas uma função booleana que a resolve.

Algumas (podem ser todas) funções são isomórficas (problemas não).

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