La preuve de Norbert Blum en 2017 selon laquelle correcte?

Norbert Blum a récemment publié une preuve de 38 pages attestant que . Est-ce correct?$P \ne NP$

Également sur le sujet: où d'autre (sur Internet) discute-t-on de son exactitude?

Remarque: l'objet de cette question a évolué au fil du temps. Voir les commentaires de la question pour plus de détails.

Comme indiqué précédemment, l'exemple de Tardos réfute clairement la preuve; il donne une fonction monotone, qui est conforme à CLIQUE sur T0 et T1, mais qui se trouve dans P. Cela ne serait pas possible si la preuve était correcte, car la preuve s'applique également à ce cas. Cependant, pouvons-nous identifier l'erreur? Voici, d'après un article sur le blog de Lipton, ce qui semble être l'endroit où la preuve échoue:

La simple erreur est un point subtil dans la preuve du théorème 6, à savoir à l'étape 1, page 31 (et aussi 33, où le cas dual est discuté) - une affirmation apparemment évidente selon laquelle contient toutes les clauses correspondantes contenues dans etc, semble faux. C N F ' ( g $C'_g$$CNF'(g)$

Pour expliquer cela plus en détail, nous devons entrer dans la méthode de preuve et approximation de Berg et Ulfberg, qui réaffirme la preuve originale de Razborov de la complexité monotone exponentielle pour CLIQUE en termes de commutateurs DNF / CNF. Voici comment je le vois:

Pour chaque nœud / porte d’un circuit logique (contenant uniquement des portes binaires OU / ET), une forme normale conjonctive , une forme normale disjonctive et des approximateurs et sont attaché. et sont que les formes normales disjonctives et conjonctives correspondantes de la sortie de porte. et sont aussi des formes disjonctives et conjonctives, mais de quelques autres fonctions, "se rapprochant" de la sortie de la porte. Ils doivent cependant avoir un nombre borné de variables dans chaque monôme pourβ 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$(inférieur à une constante r) et dans chaque clause pour (inférieur à une constante k).$C^k_g$

Il y a la notion d'une "erreur" introduite avec cette approximation. Comment cette erreur est-elle calculée? Nous ne sommes intéressés que par un ensemble T0 d’entrées pour lesquelles notre fonction totale prend la valeur 0 et T1 d’entrées pour lequel notre fonction totale prend la valeur 1 (une "promesse"). Maintenant, à chaque porte, nous ne regardons que les entrées de T0 et T1, qui sont correctement calculées (par et , qui représentent la même fonction - sortie de la porte in ) à la sortie de la porte , et regardez combien d’erreurs / erreurs sont pour etC N F ( g ) g β C k g D r g C k g D r $DNF(g)$$CNF(g)$$g$$\beta$$C^k_g$$D^r_g$, comparé à cela. Si la porte est une conjonction, la sortie de la porte peut calculer correctement plus d'entrées à partir de T0 (mais les entrées correctement calculées à partir de T1 sont éventuellement réduites). Pour , qui est défini comme une simple conjonction, il n'y a cependant pas de nouvelle erreur sur toutes ces entrées. Maintenant, est défini comme un commutateur CNF / DNF de , il pourrait donc y avoir un certain nombre de nouvelles erreurs sur T0 provenant de ce commutateur. Sur T1 également, il n'y a pas de nouvelles erreurs sur - chaque erreur doit être présente sur l'une ou l'autre des entrées de porte et, de même, sur , le commutateur n'introduit pas de nouvelles erreurs sur T1. L'analyse pour la porte OU est double.$C^k_g$$D^r_g$$C^k_g$ D r $C^k_g$$D^r_g$

Le nombre d'erreurs pour les approximateurs finaux est donc limité par le nombre de portes dans , multiplié par le nombre maximal d'erreurs possibles introduites par un commutateur CNF / DNF (pour T0) ou par un commutateur DNF / CNF (pour T1). Mais le nombre total d’erreurs doit être "grand" dans au moins un cas (T0 ou T1), car il s’agit d’une propriété des formes normales conjonctives positives avec des clauses liées par , ce qui constituait la clé de la preuve originale de Razborov (Lemma 5 dans le papier de Blum).$\beta$$k$

Alors, que fait Blum pour traiter les négations (qui sont poussées au niveau des entrées, donc le circuit ne contient toujours que des portes binaires OU / ET)?$\beta$

Son idée est de préformer les commutateurs CNF / DNF et DNF / CNF de manière restrictive, uniquement lorsque toutes les variables sont positives. Ensuite, les commutateurs fonctionneraient EXACTEMENT comme dans le cas de Berg et d’Ulfberg, introduisant le même nombre d’erreurs. Il s’avère que c’est le seul cas à prendre en compte.

Ainsi, il suit les lignes de Berg et Ulfberg, avec quelques distinctions. Au lieu d'attacher , , et à chaque porte du circuit , il attache ses modifications, , , et , c'est-à-dire les formes normales disjonctives et conjonctives "réduites", qu'il a définies comme étant différentes de etD 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)$par "règle d'absorption", en supprimant les variables négatives de tous les monômes / clauses mixtes (il utilise également à cette fin l'opération notée R, supprimant totalement certains monômes / clauses; comme nous l'avons vu précédemment, sa définition quelque peu informelle de R n'est pas vraiment le problème , R peut être précisé afin qu’il soit appliqué à chaque porte mais ce qui est supprimé dépend non seulement des deux entrées précédentes mais de l’ensemble du circuit menant à cette porte), ainsi que de leurs approximateurs et , qu'il a également introduit.${C'}^r_g$${D'}^r_g$

Il conclut, dans le théorème 5, que pour une fonction monotone, et réduits calculent réellement 1 et 0 sur les ensembles T1 et T0, au nœud racine (dont la sortie est la sortie de la totalité de la fonction dans ). Ce théorème est, je crois, correct. D N F ' g 0$CNF'$$DNF'$$g_0$$\beta$

Vient maintenant le comptage des erreurs. Je crois que les erreurs à chaque nœud doivent être calculées en comparant et réduits (qui sont maintenant deux fonctions différentes), à et comme il les a définis. Les définitions d'approximateurs correspondent aux définitions de et (étape 1) lorsqu'il mélange des variables à des variables inversées, mais lorsqu'il traite des variables positives, il utilise le commutateur comme dans le cas de Berg et d'Ulfberg (étape 2). Et effectivement, à l'étape 2, il introduira le même nombre d'erreurs possibles qu'avant (il s'agit du même commutateur et toutes les variables impliquées sont positives).D N F ' ( g ) C ' r $CNF'(g)$$DNF'(g)$${C'}^r_g$ CNF′DNF${D'}^k_g$$CNF'$$DNF'$

Mais la preuve est erronée à l' étape 1. Je pense que Blum est source de confusion , , qui viennent vraiment, comme il les définit, de approximateurs précédentes (pour les portes , ), avec des parties positives de et . Il y a une différence et par conséquent, la déclaration " contient toujours toutes les clauses contenues dans avant l'approximation de la porte g qui utilise une clause dans ou " semble être faux en général.γ 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'$

Je connais bien Alexander Razborov dont le travail précédent est extrêmement crucial et sert de fondement à la preuve de Blum. J'ai eu la chance de le rencontrer aujourd'hui et je n'ai pas tardé à lui demander son avis sur toute cette affaire, à savoir s'il en avait déjà vu la preuve ou non, et quelles seraient ses pensées à ce sujet s'il le faisait.

À ma grande surprise, il a répondu qu'il connaissait effectivement le papier de Blum mais ne se souciait pas de le lire au départ. Mais au fur et à mesure que sa notoriété augmentait, il a eu la chance de le lire et a immédiatement détecté une faille: à savoir que les raisonnements donnés par Berg et Ulfberg tiennent parfaitement pour la fonction de Tardos, et comme il en est ainsi, la preuve de Blum est nécessairement incorrect car cela contredit le noyau du théorème 6 de son article.

Ceci est affiché comme réponse de la communauté car (a) ce ne sont pas mes propres mots, mais une citation de Luca Trevisan sur une plate-forme de réseau social ou d'autres personnes sans compte CSTheory.SE; et b) quiconque ne devrait pas hésiter à le mettre à jour avec des informations actualisées et pertinentes.

Citant Luca Trevisan d'une publication publique sur Facebook (14/08/2017), répondant à une question à propos de cet article posée par Shachar Lovett :

La fonction de Andreev, qui est supposée avoir la complexité d'un circuit superpolynomial (résumé, section 7), n'est qu'une interpolation polynomiale univariée dans un corps fini, qui, si je ne manque pas quelque chose, peut être résolu par élimination gaussienne.

En réalité, ce n’est pas nécessairement un point où la preuve échoue; Luca a ensuite répondu à la question suivante (08/15/2017), après une question liée au commentaire d'Andrew ci-dessous:

Vous avez raison, les gars, j'ai mal compris la définition de la fonction de Andreev: il n'est pas clair que cela se réduit à une interpolation polynomiale

Karl Wimmer a commenté le point soulevé par Gustav Nordh (reproduit avec la permission de Karl):

Pour ajouter à cela, je ne vois pas pourquoi, dans les deux premiers paragraphes de la preuve du théorème 5, nous pouvons conclure que calcule . Je ne vois qu'une sorte de sens unique que calcule une fonction telle que implique que cette fonction est également 1.f D N F ' ( g 0 ) f = $\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$$f = 1$

Le troisième alinéa ne me permet pas non plus : sûrement et son DNF / CNF-switch calculer la même fonction, mais il ne suit pas immédiatement que le commutateur CNF DNF / calcule (parce que pourrait ne pas l'être), nous ne pouvons donc pas tirer de conclusions sur les clauses- .$\mathrm{DNF'}(g_0)$D N F ' ( g 0 ) $f$$\mathrm{DNF'}(g_0)$$f$

(A part: cette partialité est cohérente avec l'exemple de Gustav ci-dessus.)

D'un point de vue différent, un réseau standard calculant une fonction monotone pourrait sûrement calculer des fonctions non monotones au niveau de nœuds internes. Le théorème 5 ne s'applique pas aux fonctions non monotones, donc risque de ne pas calculer correctement la sous-fonction du réseau dont le noeud de sortie est (ce qui se produira pour de nombreuses fonctions non monotones). Pour cette raison, je ne suis pas convaincu que cette construction inductive de sera nécessairement correcte à la fin.$\mathrm{DNF'}(g)$$g$$\mathrm{DNF'}(g_0)$

Si je suis totalement hors de la base ici, s'il vous plaît faites le moi savoir!

D'un utilisateur anonyme, en réponse à l'argument de Karl:

DNF 'et CNF' ne sont que DNF et CNF pour f, dans lesquels les annulations de littéraux opposés sont effectuées, les réduisant ainsi à une forme plus courte. Ceci est également expliqué dans le document, et c'est un peu lourd de la définition mais c'est ce que c'est. Le théorème 5 n'est pas le problème, la viande est dans le théorème 6.

Et la réponse de Karl (que je reproduis à nouveau ici):

Je vois ce que dit anon (merci!); mon commentaire n'a pas abordé correctement ma confusion. Si est monotone et calculé à , il est de prendre , d'appliquer absorption et l' opérateur , et le représente . En utilisant cette construction "one-shot", le théorème 5 convient parfaitement - au théorème 6. Je passe sous silence cette définition deg 0 D N F ( g 0 ) $f$$g_0$$\mathrm{DNF}(g_0)$$R$f D N F ' ( g 0$\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$

Ce que je ne vois pas, c’est pourquoi la construction porte-à-porte-absorption-et- -comme-vous-allez de aux pages 27-28 fait la même chose. Cela semble nécessaire pour que l'analyse porte à porte du théorème 6 fonctionne, à moins que l'erreur de cette construction ne soit prise en compte. Je veux dire, toutes les fonctions ne peuvent même pas être représentées par un DNF avec des termes ne contenant que des littéraux non-niés ou niés, mais pour chaque nœud , semble toujours avoir cette forme. Que se passe-t-il s'il y a un nœud sur mon réseau tel que ne possède pas une telle représentation?D N F ′ ( g 0 ) g D $R$$\mathrm{DNF'}(g_0)$$g$g r e s (g$\mathrm{DNF'}(g)$$g$$\mathrm{res}(g)$

(Un autre petit (?) Point: je ne vois pas ce que fait dans la construction porte à porte au fur et à mesure; en 1.-4., Il semble que soit déjà la construction standard de DNF, mais avec absorption et appliqués)α $R$$\alpha$$R$

(réponse de anon) Je conviens que le flou dans la définition de R pourrait être un problème dans la section 6. R n'est pas explicitement défini, et à moins que son action dépende d'une manière ou d'une autre de l'ensemble du DNF (et non des valeurs de DNF 'aux portes de manière inductive) , il pourrait y avoir un problème. La preuve de Deolalikar avait un problème similaire - deux définitions différentes étaient confondues. Ici, au moins, nous savons ce qu’on entend par DNF, et si c’est la source du problème de la section 6, il peut être facile à suivre. Je ne suis pas encore entré dans la section 6, mais cela nécessite une preuve compréhensible de la part des approximateurs de Berg et Ulfberg décrits à la section 4, qui se rapportent en définitive à la construction de Razborov à partir de 1985, ce qui n’est pas facile.

Explication du fonctionnement de R:

Lorsque R est appliqué dans une étape, il n’annule que les termes qui, À CET ÉTAPE, contiendraient des littéraux opposés (il pourrait être nécessaire de suivre les littéraux négatifs). Par exemple, évaluons comme abord, pour calculer DNF 'au premier nœud ET, nous obtenons avant d’appliquer R , mais après avoir appliqué R, nous perdons le premier de la première tranche et obtenons (où le premier pourrait avoir virtuel NON si nous le suivions) . Ensuite, appliquez le deuxième ET, pour obtenir( ( x ∨ y ) ∧ ( ¬ x ∨ y ) ) ∧ ( x ∨ ¬ y ) ( x ∨ y ) ∨ ( ( x ∧ y ) ∨ ( y ∧ y ) ) x

$$(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 x ( ) ∨ ( x ∧ y ) ) , ( ( x ∧ y ) ∨ ( x $$(y) \lor (x\land y)\lor (y),$$ $y$$x$y ) ∨ ( x ∧ y ) ) ( x ∧ y $$((y) \lor (x\land y)\lor (y)) \lor ((x\land y)\lor (x\land y) \lor (x\land y)),$$ mais ensuite R supprime le toute la première tranche car elle n’a pratiquement pas été présente (dans ce cas, nous n’avions pas besoin de suivre les étapes précédentes, mais nous avons peut-être besoin en général), en laissant ou simplement $$((x\land y)\lor (x\land y) \lor (x\land y))$$ $$(x\land y)$$

La rectitude de la preuve alléguée est en discussion sur le blog de Luca Trevisan: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal- np /

En particulier "anon" a posté le commentaire pertinent suivant:

"Tardos a observé que les arguments de Razborov et Alon-Boppana sont reportés sur une fonction calculée par un circuit non monotone de taille polynomiale (la fonction est une petite variante permettant de rapprocher la fonction thêta de Lovasz du graphe). Si les arguments de Berg et d'Ulfberg également appliquer pour la fonction de Tardos (ce qui est intuitivement probable, car leur preuve semble être basée sur la preuve de Razborov), alors il est clair que l'affirmation actuelle de Blum ne peut pas être correcte. Malheureusement, l'auteur ne discute pas de ce point. "

Sur une question directe de "Mikhail", Alexander Razborov le confirme (voir le post de Mikhail): les raisonnements donnés par Berg et Ulfberg sont parfaitement valables pour la fonction de Tardos et, comme il en est ainsi, la preuve de Blum est nécessairement fausse, car elle contredit le noyau. du sixième théorème dans son article. - A. Razborov

À mon avis, cela règle définitivement la question de savoir si le papier est correct ou non (ce n’est pas correct!). Il est également important de noter qu'il semble difficile de réparer la preuve car la méthode de preuve elle-même semble imparfaite.

Update (2017/08/30) Norbert Blum a posté le commentaire suivant sur sa page arXiv:

La preuve est fausse. Je vais élaborer précisément quelle est l'erreur. Pour ce faire, j'ai besoin de temps. Je vais mettre l'explication sur ma page d'accueil

Gustav Nordh commenté par le théorème 5 (page 29). Plus précisément, la fonction

$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$

Peut-on utiliser le décodage de liste des codes de Reed-Solomon pour montrer que la fonction POLY d’Andreev est dans P, de la même manière que Sivakumar a comparé son article à son article ? Ou la fonction POLY est-elle connue pour être NP-complète?

Il a mis à jour son arXiv pour dire que sa preuve est incorrecte:

La preuve est fausse. Je vais élaborer précisément quelle est l'erreur. Pour ce faire, j'ai besoin de temps. Je vais mettre l'explication sur ma page d'accueil.

Le blog de Lipton et Regan ici a une belle discussion de haut niveau avec un commentaire intéressant sur la structure de la preuve.

Ils soulignent également le pedigree de Blum comme ayant démontré une limite inférieure à la complexité du circuit booléen qui a duré plus de 30 ans. Bien entendu, il ne s'agit que d'une "information secondaire", car les experts étudient déjà sérieusement la preuve.

Aussi, ici: https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP

Citant Alon Amit:

(opinion personnelle, le 14 août, plus tard dans la journée): Je ne pense pas que ce document résiste à un examen minutieux. Un théorème profond qui a été aussi largement étudié que P ≠ NP sera, selon toute vraisemblance, résolu par de nouvelles techniques profondes et d'une grande portée. Il n'est pas impossible que cela soit résolu avec une légère amélioration des méthodes existantes connues, mais c'est très, très, très improbable.

Il est peu probable que ce soit correct pour la raison suivante: la méthode des approximations est suffisamment générale pour que toute limite inférieure puisse être prouvée à l'aide de celles-ci. C'est un résultat dû à Razborov. Pourquoi est-ce un problème? Parce que cela signifie que la méthode des approximations ne sera pas le progrès principal, elle peut tout exprimer, la viande sera ailleurs. Il ne semble pas exister de telle substance dans le document, ce qui suggère que l'auteur fait très probablement une erreur subtile, le type d'erreur caché à l'oeil mais qui est essentiellement une hypothèse qui implique la réponse. Pour ceux qui ne sont pas des théoriciens de la complexité: il s'agit d'un très bon test d'odeur, il est tout aussi vraisemblable que de réclamer quelqu'un de construire une fusée dans son sous-sol pour se rendre sur la lune en une semaine.

Alors, où est cette erreur subtile? Sur le blog de Trevisan, il y a un commentaire de Lovett suggérant ce que cette hypothèse cachée pourrait être dans le théorème 6.

$NP-c$$P$

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

Une fonction booléenne n'a qu'une seule table de vérité, mais pas une seule expression algébrique, et aucun problème n'a une seule fonction booléenne qui le résout.

Certaines fonctions (peuvent être toutes) sont isomorphes (aucun problème).

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