Comment ne pas résoudre P = NP?

97

Il y a beaucoup de tentatives pour prouver soit ou , et naturellement beaucoup de gens réfléchissent à la question, ayant des idées pour prouver la direction dans laquelle ils veulent aller.PN PP=NPPNP

Je sais qu'il a été prouvé que certaines approches ne fonctionnent pas et que d'autres sont probablement défaillantes. Il semble également y avoir de soi-disant obstacles que de nombreuses tentatives de preuves ne parviennent pas à surmonter.

Nous voulons éviter d’enquêter sur des impasses, alors c’est quoi?

Raphaël
la source
16
Je pense que c'est mieux d'être un wiki de communauté (car il n'y a pas de réponse unique à cette question, c'est trop large).
6
@SaeedAmiri Non. Le wiki de la communauté était auparavant un alibi permettant de poser des questions qui ne convenaient pas à la plate-forme Stack Exchange, mais cela n'est plus fait .
Gilles
4
Remarque du modérateur: cette question est plus large qu'une question normale sur Stack Exchange, mais nous essayons de construire une paire canonique de questions et réponses. Si vous pensez que cette question ne devrait pas exister sous sa forme actuelle, discutez-en sur notre méta-site .
Gilles
pour une question similaire du côté opposé / constructif, voyez comment les théories et les enquêtes en informatique peuvent être résolues.
vzn
4
Wag answer: arXiv est un trésor de façons de ne pas le faire.
Pseudonyme

Réponses:

76

Je dirais que les obstacles les plus connus à la résolution de sontP=NP

  1. Relativisation (comme mentionné par Ran G.)
  2. Les preuves naturelles - sous certaines hypothèses cryptographiques, Rudich et Razborov ont prouvé que nous ne pouvons pas prouver utilisant une classe de preuves appelée preuves naturelles.PNP
  3. Algèbre - par Scott Aaronson et Avi Wigderson. Ils prouvent que les preuves que algebrize ne peut pas séparer etN PPNP

Un autre scénario que je connais bien est le résultat qu'aucune formulation de LP ne peut résoudre le TSP (cela a été prouvé par Yannakakis pour les LP symétriques et très récemment étendu aux LP en général). Voici un article de blog discutant du résultat.

Opter
la source
4
Liens pertinents: sur les obstacles en général et les exemples de jouets . Aussi, vous devriez faire attention avec votre dernière phrase, je pense qu'il serait sage d'inclure un lien vers l'article du blog qui explique pourquoi le résultat du PST non faisable par les LPs généraux ne prouve pas le , car les gens pourraient être déconcertés par le fait que LP soit complet. PPNPP
Artem Kaznatcheev
1
Si vous souhaitez améliorer la réponse (elle n'est pas tout à fait prête à accepter l'acceptation), veuillez ajouter de brèves explications et des liens vers des détails afin que le lecteur curieux sache de quoi vous parlez.
Raphaël
57

Remarque: je n'ai pas encore vérifié la réponse avec soin et il manque des parties à écrire. Considérez-le comme un premier brouillon.

Cette réponse s'adresse principalement aux personnes qui ne sont pas des chercheurs en théorie de la complexité ou dans des domaines connexes. Si vous êtes un théoricien de la complexité et que vous avez lu la réponse, veuillez me prévenir si vous remarquez un problème ou si vous avez une idée en vue d'améliorer la réponse.

Où vous pouvez trouver des solutions revendiquées de P vs. NP

  • Il y a La page P-contre-NP qui a une liste de ces demandes.
  • Les articles prétendant résoudre la question sont régulièrement publiés sur arXiv .

Autres listes sur la façon de ne pas résoudre P vs NP

Lance Fortnow, tu crois donc t'être établi P NP , 2009

Scott Aaronson, Huit signes Une réclamation P - NP prouve que c'est faux , 2010

Polymath page pour le papier de Deolalikar , où la section des lectures supplémentaires contient une belle liste de références sur le problème.


Comment ne pas approcher P vs NP

Permettez-moi de discuter de "comment ne pas aborder P vs NP" non pas dans le sens d'idées qui ne fonctionneront pas, mais dans un sens plus général. P vs. NP est un problème facile à énoncer (voir aussi ma réponse ici ):

NP = P: Pour chaque problème de décision avec un algorithme de vérificateur de temps polynomial, il existe un algorithme de temps polynomial.

ou équivalent

Il existe un algorithme temporel polynomial pour SAT.
SAT peut être remplacé par tout autre problème NP-complet .

.

Souvent, les gens simplifient à l'excès et à la philosophie, et exagèrent l'importance pratique du problème (comme indiqué ci-dessus). Ces déclarations ont souvent pour but de donner une intuition, mais elles ne sauraient en aucun cas se substituer à l'énoncé mathématique du problème.

L'efficacité théorique n'est pas la même chose que la faisabilité dans la pratique.

Permettez-moi d’abord avec des conséquences pratiques exagérées.

I. Il est possible que P = NP mais cela n’aide en pratique à aucun problème!

Disons par exemple que SAT est dans P mais que l'algorithme le plus rapide pour son temps d'exécution est . Cet algorithme n'est d'aucune utilité pratique.2264n65536+22128

II. Il est possible que P NP et nous puissions résoudre efficacement les problèmes liés à NP .

Disons par exemple que SAT n'est pas dans P mais a un algorithme avec le temps d'exécution .nlglgn

Pour donner une entrée qui donnerait vous devez utiliser plus d'électrons que l'on pense être dans l'univers. Donc, l'exposant est essentiellement .2lgn>62

Le point principal ici est que P est un modèle simple abstrait de calcul efficace, la complexité dans le pire des cas est un modèle simple abstrait d'estimation du coût d'un calcul, etc. Tous ces éléments sont des abstractions, mais personne dans la pratique n'envisagerait un algorithme. comme celui de (I) ci-dessus comme un algorithme efficace vraiment. P est un beau modèle abstrait, il a de belles propriétés, il facilite les problèmes techniques et il est utile. Cependant, comme toute abstraction mathématique, elle cache des détails qui, dans la pratique, peuvent nous intéresser. Il existe différents modèles plus raffinés, mais plus le modèle devient compliqué, moins il est agréable de discuter.

En pratique, l’important pour les gens est de calculer une réponse au problème dans les cas où ils tiennent à utiliser une quantité raisonnable de ressources. Il existe des tâches dépendantes et doivent être prises en compte

Essayer de trouver de meilleurs algorithmes pour des instances pratiques de problèmes difficiles à résoudre est une tentative intéressante et utile. Il existe des algorithmes heuristiques de résolution SAT utilisés dans l'industrie et capables de résoudre des instances pratiques de SAT avec des millions de variables. Il y a même un concours international SAT .

(Mais il existe également de petites instances concrètes dans lesquelles tous ces algorithmes échouent et échouent assez mal, nous pouvons en fait prouver que tous les solveurs SAT modernes et ultramodernes prennent un temps exponentiel pour résoudre des instances simples comme le principe de Pigeonhole propositionnel .)

Gardez à l'esprit que l' exactitude et la durée d'exécution des programmes ne peuvent pas être obtenues simplement en exécutant le programme sur des instances . Peu importe combien de fois vous essayez, aucun montant n'est suffisant. Il y a une infinité d'intrants possibles et vous devez montrer l'exactitude et l'efficacité (le temps d'exécution est polynomial) du programme pour chacun d'entre eux. En bref, vous avez besoin d’une preuve mathématique d’exactitude et d’efficacité. Si vous ne savez pas ce qu'est une preuve mathématique, vous devez d'abord apprendre quelques notions de base en mathématiques (lire un manuel de mathématiques / combinatoire / théorie des graphes discrète, il s'agit d'un bon sujet pour en savoir plus sur ce qui est considéré comme une preuve mathématique).

Faites également attention aux autres affirmations sur P vs NP et aux conséquences de ses réponses. De telles revendications sont souvent basées sur des simplifications similaires.

Les théoriciens de la complexité ne se soucient pas vraiment d'une réponse à P vs NP!

J'ai exagéré un peu. Bien sûr, nous nous soucions d’une réponse à P vs. NP. Mais nous nous en soucions dans un contexte. P vs. NP est notre problème phare mais ce n'est pas le but ultime. C'est un problème facile à énoncer, qui fait appel à de nombreuses idées fondamentales. Il est utile pour expliquer le type de questions qui nous intéresse aux personnes qui ne sont pas familières avec le sujet. Mais nous ne cherchons pas une réponse un peu oui / non à la question.

Nous cherchons à mieux comprendre la nature du calcul efficace . Nous pensons que la résolution de la question s’accompagnera d’une telle compréhension et c’est la véritable raison pour laquelle nous nous en soucions. Cela fait partie d'un énorme corpus de recherche. Si vous voulez avoir un aperçu de ce que nous avons déjà, regardez un bon manuel de théorie de la complexité, par exemple Arora et Barak, « Théorie de la complexité: une approche moderne » ( version préliminaire ).

Supposons que quelqu'un dispose d'une preuve complètement formelle chiffrée de P NP et que nous pouvons en vérifier l'exactitude avec un degré de confiance très élevé en sélectionnant et en déchiffrant quelques éléments de la preuve (voir Théorème Zero-Knowledge Proof et PCP ). . Donc, nous pouvons vérifier la réclamation avec une probabilité d'erreur inférieure à celle d'un météore qui frappe notre maison, nous sommes tout à fait sûrs que la preuve est correcte et P = NP, mais nous ne connaissons pas la preuve. Cela ne créera pas beaucoup de satisfaction ou d’excitation pour nous. La preuve formelle elle-même ne sera pas aussi satisfaisante. Ce que nous recherchons n'est pas une preuve formelle, nous cherchons à comprendre.

En bref, du point de vue d'un théoricien de la complexité

P vs. NP n'est pas un casse-tête avec une réponse oui / non. Nous cherchons une réponse à P vs. NP car nous pensons que cela nous permettra de mieux comprendre la nature du calcul efficace. Une réponse sans avancée majeure dans notre compréhension n’est pas très intéressante.

Trop souvent, des non-experts ont réclamé des solutions pour P contre NP, et ces réclamations souffrent généralement de problèmes qu’ils n’auraient pas résolus s’ils lisaient simplement un manuel standard sur la théorie de la complexité.

Problèmes courants P = NP

Les affirmations de P = NP semblent être plus courantes. Je pense que ce qui suit est le type le plus commun. Quelqu'un a une idée, écrit un programme et le teste sur quelques instances. Il pense que le temps est polynomial et qu'il résout correctement un problème NP-complet. Comme je l'ai expliqué ci-dessus, aucun test ne montrera P = NP. P = NP nécessite une preuve mathématique , pas seulement un programme qui semble résoudre un problème NP-complet en temps polynomial.

Ces tentatives souffrent généralement de l'un des deux problèmes suivants:

I. l'algorithme n'est pas vraiment polynomial.

II. l'algorithme ne résout pas toutes les instances correctement.

Signes qu'un argument P NP n'est pas correct

[à écrire]

Comment vérifier que votre algorithme ne fonctionne pas vraiment

Vous ne pouvez pas montrer que votre algorithme fonctionne correctement en testant. Mais vous pouvez montrer que cela ne fonctionne pas correctement en testant! Voici comment vous pouvez vous assurer que votre algorithme n’est pas correct si vous êtes prêt à travailler.

Commencez par écrire un programme permettant de convertir les instances de SAT (au format CNF standard) en un problème NP-difficile que vous résolvez. La SAT est l’un des problèmes NP-difficiles les plus étudiés et il est généralement facile de passer d’un autre problème à la SAT. Deuxièmement, prenons les exemples avec lesquels les solveurs SAT à la pointe de la technologie ont des difficultés (par exemple, prenons les exemples de la concurrence SAT) et transmettez-les à votre algorithme pour voir comment il fonctionne. Essayez des instances dures connues comme le principe de pigeonhole propositionnel (et ne trichez pas en les codant en tant que cas spéciaux), des instances cryptographiques (comme les défis d'affacturage RSA ), des instances aléatoires k-SAT près du seuil , etc.

De même, vous pouvez vérifier que votre algorithme n'est pas efficace. Par exemple, si vous pensez que le temps d'exécution de votre algorithme n'est pas mais qu'il faut des jours pour résoudre une instance de disons de taille 1000. Corrigez la limite supérieure polynomiale de temps d'exécution que vous pensez que votre algorithme a. Prenez les instances et estimez le temps que votre algorithme prendra pour les résoudre et vérifiez si elles correspondent à vos estimations.10n2

Comment vérifier votre idée algorithmique P = NP ne peut pas fonctionner

Si vous faites cela, vous serez à peu près sûr que votre algorithme ne fonctionnera pas (s'il fonctionne mieux que les solveurs SAT à la pointe de la technologie, participez au prochain concours et de nombreuses personnes seraient intéressées par l'étude de votre algorithme et de vos idées).

Maintenant, vous savez que cela ne fonctionne pas vraiment, mais cela ne suffit pas. Tu veux savoir pourquoi,

la raison pour laquelle mon algorithme ne fonctionne pas est un petit problème qui peut être corrigé ou existe-t-il une raison fondamentale pour laquelle il ne peut pas fonctionner?

Parfois, le problème de l'algorithme est simple et on peut identifier conceptuellement ce qui ne va pas. Le meilleur résultat est que vous comprenez la raison pour laquelle votre idée ne peut pas fonctionner. Souvent, ce n'est pas le cas, votre idée ne fonctionne pas mais vous ne pouvez pas comprendre pourquoi. Dans ce cas, gardez à l'esprit:

Comprendre pourquoi une idée ne peut pas fonctionner peut être plus difficile que de résoudre P vs NP!

Si vous parvenez à formaliser suffisamment votre idée, vous pourrez peut-être prouver que certaines idées sont limitées (par exemple, certains résultats indiquent qu'une formalisation particulière de l'algorithme glouton ne peut pas résoudre les problèmes NP-complets). Cependant, c'est encore plus difficile, et vous n'avez pas beaucoup de chance si vous n'avez pas lu un manuel de théorie de la complexité standard.

Parfois, il n’ya même pas une idée conceptuelle claire de la raison pour laquelle l’algorithme devrait fonctionner, c’est-à-dire qu’il est basé sur des heuristiques mal comprises . Si vous n'avez pas une idée conceptuelle claire de la raison pour laquelle votre algorithme devrait fonctionner, vous n'aurez peut-être pas beaucoup de chance de comprendre pourquoi il ne fonctionne pas!

Problèmes courants liés aux revendications de P NP

Bien que la plupart des experts pensent que P NP est plus probable que P = NP, de telles affirmations semblent moins fréquentes. La raison en est que la démonstration des limites inférieures semble être une tâche plus ardue que la conception d’algorithmes (mais souvent, prouver que les limites inférieures et les limites supérieures sont intrinsèquement liées ).

Problème 1: l'auteur ne connaît pas la définition de P et NP ou, pire encore, ne comprend pas ce qu'est une preuve mathématique. Parce que l'auteur manque de formation mathématique de base, il ne comprend pas quand on lui dit que ce qu'il présente n'est pas une preuve (par exemple, les étapes ne suivent pas les précédentes).

Numéro 2: l'auteur confond "on ne sait pas comment" avec "l'impossibilité mathématique". Par exemple, ils font diverses hypothèses injustifiées et lorsqu'on leur demande "pourquoi cette affirmation est vraie?" ils répondent "comment cela peut-il être faux?". L’un des plus courants est de supposer que tout programme qui résout le problème doit passer par des étapes particulières, par exemple, il doit calculer des valeurs intermédiaires particulières, car il ne peut penser à une autre façon de résoudre le problème.

[à compléter]

Signes qu'un argument P NP n'est pas correct

[à écrire]

Comment vérifier votre idée de NP P ne peut pas fonctionner

Si une revendication ne souffre pas de ces problèmes fondamentaux, son rejet devient plus difficile. Au premier niveau, on peut trouver une étape incorrecte dans l'argument. La réponse typique de l'auteur est que je peux résoudre ce problème et que cela peut continuer. Comme pour les solutions P = NP, il est souvent très difficile de trouver un problème fondamental avec une idée qui peut montrer qu’elle ne peut pas fonctionner, en particulier lorsque l’idée elle-même est informelle.

Dans le meilleur des cas, si nous pouvons formaliser l’idée et identifier l’obstacle qui montre que l’idée ne peut pas fonctionner, nous avons prouvé un nouveau résultat de barrière (c’est ainsi que les tentatives pour prouver que P NP utilise des limites inférieures du circuit mènent à la barrière Natural Proofs ).

Kaveh
la source
Même si j'aime bien la page P-versus-NP, je trouve ennuyeux de ne pas savoir quelles preuves ont été retirées par leurs auteurs. Pour certains liens arXiv, vous trouvez des avis explicites "ce document a été retiré" sur arXiv. Je suis à peu près sûr qu'il y a plus de preuves retirées que les papiers arXiv avec notification explicite. OK, je suis conscient que les preuves retirées ne doivent pas être surestimées, car retirer une "tentative de preuve antérieure" n'implique pas que les mêmes auteurs ne réessayeront pas plus tard. Mais garder le silence sur les tentatives de preuves retirées donne toujours une impression biaisée.
Thomas Klimpel
Quelques-uns des auteurs "cinglés" n'ont jamais "retiré" leurs papiers. Le point inexprimé de la liste woegorgi est qu’il est nettement moins qualitatif que les papiers arxiv. mais, d'accord, je souhaite que woegorgi puisse ajouter quelques informations supplémentaires et qu'il puisse être un peu plus souple dans son montage. par exemple, il n'a pas mis mon contour P vs NP sur la liste même après l'avoir envoyé par courrier électronique, bien qu'il ait récemment posté un autre élément sur la preuve fukuyama liée à une longue discussion cstheory.se.
vzn
1
J'apprécie que vous revisitez cela! On dirait que j'ai prématurément reconnu la prime à la mauvaise personne après tout. ;) Notez que vous pouvez utiliser stackedit.io pour préparer une publication dans le temps. Dans l'attente du reste du post!
Raphaël
34

La technique la plus courante qui ne peut pas être utilisée est la relativisation , c’est-à-dire l’utilisation d’un TM avec accès Oracle.

L’impossibilité découle d’un article de Theodore Baker, John Gill, Robert Solovay qui montrent l’existence de deux oracles (langues), et tels que et .B P A = NP A P BNP BABPA=NPAPBNPB

Ainsi, si on peut relativiser une preuve pour, par exemple, , cela signifierait que pour tous les oracles , ce qui contredit l'existence d' .O P ONP O APNPOPONPOA

Cela signifie notamment que la diagonalisation ne peut pas être utilisée pour prouver car ces preuves peuvent être relativisées (voir par exemple ces notes de cours) .P=?NP

A sonné.
la source
1
Juste pour corriger complètement, diagonalisation signifie ici simple diagonalisation directe . Voir cette question
Kaveh
1
La relativisation n’est donc pas la technique de la preuve, mais l’effet qui casse une preuve? Pouvez-vous donner / créer un lien vers un exemple de preuve pouvant être relativisée?
Raphaël
2
oui, la relativisation n'est pas une technique de preuve, c'est une propriété d'une preuve (n'étant pas formelle ici d'ailleurs). si la preuve fonctionne sans changement lorsque toutes les machines sont remplacées par des machines Oracle, la preuve est relativisée. vous pouvez vous convaincre que la preuve du théorème de la hiérarchie temporelle relativise dans ce sens, par exemple.
Sasho Nikolov
10

Je suggère de lire ce billet de blog de Lance Fortnow :

  1. Donc, vous pensez que vous avez réglé P verus NP Vous avez tort. Comprenez-le. Parfois, vous pouvez toujours récupérer quelque chose d’intéressant dans votre preuve imparfaite.
  2. Vous pensez que la preuve est correcte. Votre croyance est incorrecte. Retournez à l'étape 1.
  3. Faites-vous des hypothèses ou des raccourcis, même apparemment petits et évidents? Utilisez-vous des mots tels que "clairement", "évidemment", "facile à voir", "devrait", "doit" ou "probablement"? Vous prétendez régler peut-être la question la plus importante de toutes les mathématiques. Vous n'obtenez pas de suppositions. Retournez à l'étape 1.
  4. Comprenez-vous vraiment le problème P versus NP? Pour montrer P ≠ NP, vous devez trouver une langue L dans NP telle que pour chaque k et chaque machine M exécutée dans le temps (n = longueur d'entrée), M ne calcule pas correctement. L est un ensemble de chaînes. Rien d'autre. L ne peut pas dépendre de M ou k. M peut être n'importe quel programme traitant des chaînes de bits. M peut agir complètement différemment de ce que vous avez défini dans la définition de L. Revenez à l’étape 1.nk
  5. Vous soumettez votre article à une archive en ligne. Peut-être que certaines personnes vous diront ce qui manque ou ce qui ne va pas dans votre papier. Cela devrait vous amener à passer à l’étape 1. Mais au lieu de cela, vous apportez quelques modifications insignifiantes à votre papier et à sa publication.
  6. Finalement, les gens ignorent votre papier. Vous vous demandez pourquoi vous ne recevez pas la gloire et la fortune.
  7. Vous soumettez votre article à un journal.
  8. Le papier est rejeté. Si vous êtes intelligent, vous retournerez à l’étape 1. Mais si vous étiez intelligent, vous n’auriez jamais atteint l’étape 7.
  9. Vous vous plaignez à l'éditeur soit que l'éditeur ne comprend pas la preuve, soit qu'elle est facilement corrigée. Vous êtes choqué qu'un éditeur ou un journal respectable traite votre article de cette façon.
  10. Vous soumettez à nouveau le document, faites appel, essayez d'autres journaux, en vain.
  11. Vous êtes convaincu que "l’établissement" supprime volontairement votre document, car notre domaine deviendrait beaucoup moins intéressant si nous réglions le problème P / NP, nous devons donc le garder ouvert à tout prix.
  12. Si je vous disais le contraire, vous me croiriez?
Kaveh
la source
7
La question demande «des approches dont il a été prouvé qu'elles ne fonctionnent pas» et des approches «qui ont des antécédents d'échec», et cette réponse ne mentionne aucune approche.
Tsuyoshi Ito
6
Mon argument est que, parce que l'article de blog ne répond pas du tout à la question, il est inutile de le copier-coller.
Tsuyoshi Ito
7
Cela ne répond effectivement pas à la question. Le billet de blog est une liste sournoise d’étapes de type P = NP? la manivelle passe à travers. Bien que divertissant, cela ne me fournit pas de théories spécifiques qui se sont avérées incapables de séparer (ou de s'effondrer) de P et de NP.
Raphaël
4
Que dis-tu de ça? Cette question demande des barrières pour prouver P! = NP. Les obstacles dans cette réponse (comme indiqué dans les commentaires) sont "supposer quelque chose", "mauvaise interprétation", "dire quelque chose est clair", "croire en quelque chose". Ces obstacles sont trop généraux en ce sens qu'ils constituent des obstacles à la preuve de quoi que ce soit et non pas spécifiquement des obstacles à la preuve de P! = NP.
Tyson Williams
1
les commentaires en cours de validité manquent tous un point fondamental. Le blog a été écrit par Lance Fortnow, un théoricien expert en complexité et autorité mondiale sur le sujet; il vient de sortir un nouveau livre sur P vs NP Golden Ticket . il parle donc essentiellement d’expérience personnelle.
vzn
2

C’est un peu obscur / profond / difficile / angle interne / référence / torsion concernant les approches via des circuits datant des années 1980 qui m’avait été signalé il y a des années par Luca Trevisan ailleurs dans le cyberespace, et réitéré par Stasys Jukna, auteur d’un excellent référence proche du sujet, Complexité des fonctions booléennes: avancées et frontières (Algorithms and Combinatorics, Vol. 27 ).

On peut voir une tendance antérieure dans certaines réflexions de Razborov qui a finalement abouti au document Natural Proofs (appelé "naturalisation"). La référence [273] est très technique et difficile et ne semble pas être citée, construite / développée, ou beaucoup réitérée par des papiers / livres ultérieurs, bien que les preuves naturelles puissent être considérées comme une large généralisation ultérieure. l'extrait est de John E Savages excellente référence Models of Computation p457

Ω(n2)n

[270] AA Razborov, «Limites inférieures de la complexité monotone de certaines fonctions booléennes», Dokl. Akad. Nauk SSSR (Soviet Math. Dokl.) 281 (1985), 798–801 (en russe); Traduction anglaise en mathématiques soviétiques. Dokl. 31 (1985), 354–357

[271] AA Razborov, «Limite inférieure de la complexité du réseau monotone du permanent logique», Mat. Zametki 37 (1985), 887 à 900 (en russe); Traduction anglaise en maths. Notes 37 (6) (1985), 485–493.

[273] AA Razborov, «Sur la méthode des approximations», Proc. 21ème Ann. ACM Symp. Théorie de l'informatique (1989), 167–176.

vzn
la source
2
Je ne vois pas comment cela répond à la question "comment ne pas prouver P? = NP". À l'heure actuelle, cela ressemble plus à une sorte de spéculation sur les pensées de quelqu'un.
Juho
2
Bien sûr, je ne fais que suggérer de rendre tout cela explicite. La complexité des circuits n’est même pas essentielle pour les étudiants de premier cycle; certains éléments sont donc justifiés. Il est juste de s’attendre à ce que le lecteur ne soit pas un expert en théorie de la complexité.
Juho
@juho ok. Une fois que j'ai vu le livre Savage [très centré sur le circuit] utilisé dans une classe de premier cycle, cela m'a aussi surpris. a accepté son matériel avancé d'où le libellé de la 1ère phrase. quant à la "spéculation sur les pensées", il n'y en a aucune, sauf en citant les propres pensées de Razborov telles qu'elles sont écrites / consignées dans ses propres papiers.
vzn
1
et en passant, il s’agit d’une question très complexe (pas vraiment de premier cycle) et d’autres réponses sont avancées et généralement en dehors du premier cycle.
vzn