La preuve de Norbert Blum en 2017 selon laquelle correcte?

232

Norbert Blum a récemment publié une preuve de 38 pages attestant que . Est-ce correct?PNP

É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.

Warren Schudy
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Bjørn Kjos-Hanssen

Réponses:

98

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 )CgCNF(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 ggβCNF(g)DNF(g)CgkDgrCNFDNFDgrCgkDgr(inférieur à une constante r) et dans chaque clause pour (inférieur à une constante k).Cgk

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 gDNF(g)CNF(g)gβCgkDgr, 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.CgkDgrCgk D r gCgkDgr

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).kβ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)?β

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 ' rCNF(g)DNF(g)CgkDgrgβCNF(g)DNF(g)CgkDgrCNF(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.CgrDgr

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 βCNFDNFg0β

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 gCNF(g)DNF(g)Cgr CNFDNFDgkCNFDNF

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 γ ' 2γ1γ2h1h2CNFβ(h1)CNFβ(h2)CgCNFβ(g)γ1γ2

idolvon
la source
2
semble être le même commentaire sur le blog RJL rjlipton.wordpress.com/2017/08/17/… avez-vous écrit cela? voulait ajouter une idée: que se passe-t-il si la clé est de considérer T0 / T1 de toutes les conversions égales à 1 bits par rapport au format cnf-dnf? il est connu par Berkowitz 1982 cela est suffisant pour séparer P vs NP voir « complexité des fonctions de tranche » / Wegener sciencedirect.com/science/article/pii/0304397585902099
VZN
6
@vzn L'auteur de ce commentaire sur le blog est "vloodin". L'auteur de cette réponse est "idolvon". Une permutation des lettres laisse deviner que les auteurs ne sont pas trop différents.
Clement C.
2
Juste curieux, y a-t-il eu d'autres communications publiques de Blum après le téléchargement du document sur l'arxiv?
Matt
9
@Matt Blum a rétracté le document et affiché le commentaire suivant sur la page arXiv du document: "La preuve est fausse. Je vais préciser quelle est l'erreur. Pour ce faire, j'ai besoin d'un peu de temps. Je mettrai l'explication sur homepage "
Gustav Nordh
Cette réponse a été confirmée comme correcte par Scott Aaronson, citant d'autres relecteurs (non nommés): scottaaronson.com/blog/?p=3409
cuniculus
95

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.

Mikhail
la source
2
Ce serait formidable si vous pouviez élaborer sur ce sujet. La fonction de Tardos est-elle connue pour être en P?
Thomas
5
La fonction Tardos est en P et est une approximation de la fonction thêta de Lovasz, qui, pour un complément graphique, est comprise entre le nombre de cliques et le nombre chromatique. La fonction réelle de Lovasz thêta est une fonction monotone d'un graphe. Cependant, la question est de savoir si cette approximation donne lieu également à une fonction monotone d’un graphe (seule la fonction monotone invaliderait la preuve). Quelqu'un peut-il nous donner la référence au papier Tardos où cela est défini, s'il vous plaît?
idolvon
7
@idolvon Vous voulez dire ceci: cs.cornell.edu/~eva/… Il est explicitement indiqué que la fonction est une fonction monotone calculable poly-time
PsySp
12
Merci! Cela règle fondamentalement le problème - la preuve de Bloom doit être fausse. Maintenant, il pourrait être intéressant de localiser une erreur. J'examinerai et posterai un commentaire sur Lipton's, comme au bon vieux temps, selon le prof. p Les souhaits du piccher.
idolvon
1
@ idolvon Oui, je le pensais aussi. Les arguments de Blum devraient porter la fonction φ telle que définie dans l'article qui dit qu'il est monotone et poly-temps calculable (trivial par sa définition).
PsySp
41

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 = 1DNF(g0)fDNF(g0)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- .DNF(g0)D N F ' ( g 0 ) ffDNF(g0)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.DNF(g)DgDNF(g0)

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 ) Rfg0DNF(g0)Rf D N F ' ( g 0 )DNF(g0)fDNF(g0)

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 NRDNF(g0)gg r e s (g)DNF(g)gres(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)α RRα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 (

(xy)(¬xy)(x¬y)
((xy)(¬xy))(x¬y)
(xy)((xy)(yy))
xy x ( ) ( x y ) ) , ( ( x y ) ( x
(y)(xy)(y),
yxy ) ( x y ) ) ( x y )
((y)(xy)(y))((xy)(xy)(xy)),
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
((xy)(xy)(xy))
(xy)
Clement C.
la source
6
Je suis sceptique à ce sujet (mais n'utilisez pas Facebook pour dire quoi que ce soit là-bas) - La fonction de Andreev (dans l'article) est donnée sous la forme d'un graphe bipartite avec des ensembles de sommets gauche et droit égaux à GF (q), plus un ensemble de bords arbitraires et un degré lié. La question est de savoir s’il existe un moyen de choisir, pour chaque sommet de gauche, l’un de ses voisins, de sorte que la fonction induite (de gauche à droite) soit un polynôme de degré faible. Le commentaire de Luca s'applique une fois que nous avons un bon choix de voisin pour chaque sommet gauche (car il ne s'agit que d'une interpolation polynomiale), mais je ne vois pas trop comment faire un bon choix.
Andrew Morgan
@AndrewMorgan J'ai mis à jour la réponse CW.
Clement C.
@ Karl Wimmer: en ce qui concerne la météo, DNF ′ (g0) calcule f, il faut utiliser le fait que f est monotone, je pense. Le théorème 5 suppose que f est monotone.
idolvon
confus! est-ce que tout cela cite le post facebook? en cliquant sur le lien facebook de shachar lovett ci-dessus, certaines des réponses ci-dessus me sont visibles, mais d'autres ne le sont pas. par exemple Karl Wimmer. est-ce dû à un filtrage des réponses d'amis sur facebook? Si c'est le cas, c'est décevant et ce n'est pas un très bon endroit pour une discussion publique. peut-être que quelqu'un peut faire une capture d'écran? :( ou citez-vous des choses qui ne se trouvent pas sur Facebook? Merci de faire attention / de citer des citations / urls
vzn
Oh! des recherches plus approfondies, vous citez également les réponses du billet de blog de baez qui contient la réponse de Wimmers,
vzn
36

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
la source
3
J'ai posté ceci comme une réponse car je n'ai pas encore les privilèges pour poster des commentaires.
Gustav Nordh
11
Oui, c'est ce que je comprends (mais je peux me tromper). La fonction de Tardos est une fonction monotone qui vaut 1 sur les k-cliques et 0 sur les graphes complets (k-1) -partites. Autant que je sache, Berg et Ulfberg utilisent UNIQUEMENT ces propriétés dans leur preuve d’approximation CNF-DNF pour CLIQUE, ce qui prouve donc que la fonction de Tardos a une complexité monotone exponentielle. Le théorème 6 de Blum dit que les limites inférieures de complexité monotone par approximation CNF-DNF pour les fonctions monotones, donnent la même limite inférieure NON monotone. Par conséquent, la fonction de Tardos a une complexité exponentielle selon le théorème 6 (ce qui est faux).
Gustav Nordh
5
Dans ce cas, il semble que régler ce point devrait être une priorité pour le moment ... Je ne pense pas être suffisamment compétent ou informé pour le faire, mais (les doigts croisés, ce qui n'aide pas la dactylographie), les autres le sont.
Clement C.
3
Où cette fonction Tardos est-elle définie? Quelqu'un peut-il donner une référence au document? Clairement, il existe des fonctions non monotones séparant T0 et T1 qui se trouvent dans P (il est facile de construire dit vérifiant si nous avons un graphe complet avec k nœuds), mais la fonction de Tardos est-elle monotone? Si monotone et sépare T0 et T1, cela invaliderait la preuve. Mais si ce n'est pas monotone, alors la preuve peut toujours être correcte.
Idolvon
4
La fonction de Tardos est définie dans son très court article situé ici: cs.cornell.edu/~eva/… De plus, les propriétés de la fonction de Tardos sont discutées en détail dans [S. Jukna, complexité de la fonction booléenne p. 272]
Gustav Nordh
25

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

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

1xy1βxyβg0

DNFβ(g0)β

xy(xy)

DNFβ(g0)fDNFβ(g0)xfx=1f(x,y)=1R

kdog
la source
2
Il semble que DNF 'pour cette formule est (x AND y) - forme DNF complet, annule les termes triviaux et applique absorption
idolvon
2
DNF
2
La définition des pages 27-28 implique l’utilisation de l’opérateur R, qui n’est défini que par la phrase vague "a pour origine un monôme trivial". Si nous supposons que cela signifie "serait annulé si les littéraux étaient maintenus jusqu'à ce stade", les définitions sont les mêmes. Dans tous les cas, vous auriez besoin de quelques interprétations pour R. Puisque R est si crucial au chapitre 6, la bonne interprétation est importante, et il y en a une qui est inductive.
idolvon
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

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?

Lance Fortnow
la source
10
Lance, je ne réponds pas à vos questions. En juin 1986, "Le problème ouvert du mois" de David Johnson demandait si le problème d'Andreev était NP-complet. Voir la colonne NP-complétude de David dans Journal of Algorithms 7: 2, p. 289-305. Je ne sais pas s'il y a déjà eu une résolution.
Ravi Boppana
1
L'article de Johnson datant de 1986 est antérieur aux techniques de reconstruction polynomiale et aux résultats de décodage par liste des années 90.
Lance Fortnow
1
Voici mon idée en utilisant la notation de la section 7 du document de Norbert Blum. Un polynôme p qui constitue une solution au problème POLY pourrait être considéré comme un mot de code de Reed-Solomon. Choisissez une fonction f en choisissant de manière aléatoire une arête de chaque sommet en A. Ce f devrait correspondre à p de manière nettement supérieure à une fraction 1 / q des entrées. Ensuite, nous pouvons utiliser le décodage de liste sur f pour créer une liste polynomiale de possibilités pour p et vérifier chacune d’elles.
Lance Fortnow
1
qddpdqlogq1q
4
@Matt En supposant que je lise correctement ce qui précède, cette fonction est celle qui permet à Blum de revendiquer une complexité prouvée des circuits superpolynomiaux. Mais si elle est en P, elle doit avoir une complexité de circuit polynomiale, en contradiction avec la prétendue preuve P vs NP.
Clement C.
14

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.

Mehrdad
la source
9

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.

Kodlu
la source
3

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.

Jack
la source
11
C'est un non-argument (une opinion valide, et que je reconnais partager, mais pas un argument valable, et c'est ce que je pense que nous devrions avoir ici). Ce genre de choses est déjà arrivé .
Clement C.
8
Oui, je ne discutais pas. Répondez simplement à la question "où ce document est-il discuté", puis résumez la discussion jusqu'à ce point.
Jack
2

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.

Sceptique
la source
point intéressant / pertinent; fyi razborovs "no go" thm is "sur la méthode des approximations" (1989) people.cs.uchicago.edu/~razborov/files/approx.pdf mais estime que cette preuve n’est pas très bien analysée. il faut bien comprendre si ses conditions énoncées vont au-delà des mots "méthode d'approximation" qui sont passés par des révisions / développements / améliorations, etc. depuis sa création par razborov. ces conditions exactes ne sont apparemment pas beaucoup analysées par les chercheurs ultérieurs. L'autre barrière majeure est celle de razborov / rudich preuves naturelles en.wikipedia.org/wiki/Natural_proof
vzn
downvoted parce que le contenu de cette réponse a déjà été abordé dans les réponses précédentes.
vérification
-2

NPcP

CffCm

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=Pmmfff

Ixer
la source