Rappelons les faits. L'Encyclopædia Britannica en version papier coûte, d'après certaines sources, environ 1400$. D'après Amazon, qui la facture à environ $2000, elle pèse 61 kg, et occupe à la livraison un volume d'environ 80×57×55 cm. Autant dire que ça ne passe pas inaperçu dans une bibliothèque ! Je me rappelle d'intérieurs de classe moyenne anglo-saxonne où laBritannica trônait bien en évidence dans le séjour : peut-être faut-il voir, comme certains l'ont suggéré, une certaine volonté de prouver l'appartenance au monde cultivé, ou encore le désir d'avoir fait ce qu'il fallait pour que les enfants réussissent à l'école.

Par comparaison, l'abonnement à Britannica en ligne coûte $70 par an, et, si j'ai bien compris, le produit en ligne est plus riche en articles que la version papier. Qui plus est, il est plus facile à consulter : plus besoin d'avoir plusieurs volumes ouverts dès que l'on veut suivre un renvoi. Le calcul est vite fait : d'un côté, un mastodonte de papier, difficile à loger et à déménager, de l'autre un produit en ligne pratique, dont il faut plus de 20 ans d'abonnement pour atteindre le prix du produit papier. Nul besoin de Wikipédia, donc, pour expliquer que la version en ligne cannibalise naturellement la version papier.

Bien sûr, on peut valablement argumenter que si Britannica n'avait pas ouvert de version en ligne, elle se serait condamnée face à la concurrence des encyclopédies en ligne, notamment Wikipédia. Toutefois, il me semble important de noter que l'abandon du papier est plus un problème de passage à un médium plus pratique, comme le passage au livre relié par rapport aux rouleaux, qu'un problème de concurrence.

Passons maintenant au sujet de la couverture thématique de Wikipédia vs celle de Britannica. Je n'ai évidemment pas le loisir de me livrer à une étude approfondie et scientifique ; aussi, comme d'autres enseignants ayant discuté de comparaisons entre Wikipédia et des encyclopédies conventionnelles, j'examinerai rapidement quelques articles portant sur des sujets que j'enseigne, en évitant toutefois de prendre mes sujets précis de recherche : on m'objecterait alors, peut-être à juste titre, que j'ergote sur des points dont je suis spécialiste. Prenons donc la logique, la calculabilité, et la complexité.

J'apprécie beaucoup l'article de Britannica sur l'histoire de la logique. Il présente tant un bon historique du domaine et qu'un bon panorama des problématiques contemporaines (y compris la théorie de la récursion et la calculabilité, sans lesquelles il est il me semble difficile de parler valablement des théorèmes d'incomplétude de Gödel). Je conseille sa lecture.

L'argument classique en faveur de la supériorité de Britannica sur Wikipédia est que ses articles sont rédigés par des experts ; mais un argument qui me semble tout à fait recevable et important est qu'ils ont une bonne cohérence interne et sont professionnellement relus et édités, alors que les articles de Wikipédia sont rédigés « par comité », et sont rarement relus et restructurés in extenso. Il me semble que pareil article serait impossible sur Wikipédia.

Qu'entends-je par là ? La rédaction d'un article de synthèse sur un sujet donné impose la fixation d'un plan, le choix de ce que l'on va évoquer en détail, ignorer, ou renvoyer à d'autres articles. Ces choix sont assez arbitraires : plusieurs spécialistes du sujet pourront avoir des opinions différentes ; qui plus est, on pourra vouloir rédiger l'article différemment suivant le public visé (par exemple, on ne présente pas la théorie de la calculabilité de la même façon à des gens qui ont une formation en mathématiques ou en programmation informatique). Cependant, ce qui est important, c'est qu'une fois un choix fixé, on s'y tienne, sinon on obtient un résultat incohérent, déséquilibré, avec des redites ou des omissions. Sur Wikipédia, il est difficile de maintenir cette cohérence, de par la possibilité pour des auteurs nombreux d'introduire des changements à tout instant. Notons que cette faiblesse n'a que peu de rapport avec la compétence des auteurs : l'effet de la « rédaction par comité » est sensible y compris quand le comité est formé de spécialistes.

J'ai été en revanche très désagréablement surpris du traitement réservé par Britannica à la théorie de la complexité algorithmique, domaine scientifique très actif depuis les années 1970, d'ailleurs absolument ignoré par Universalis, la filiale française de Britannica, et dont le problème emblématique, la question de la séparation des classes P et NP, a été érigé au rang de « grand problème du millénaire » en mathématiques. Britannica limitant sa couverture de la complexité à cet unique problème (pas de discussion de PSPACE, par exemple), voyons justement l'article P versus NP problem...

Dans les grandes lignes, cet article est correct et donne notamment dans son premier paragraphe une bonne caractérisation intuitive des classes P et NP. Une réserve cependant : l'assimilation de « temps polynomial » à « tractable », c'est-à-dire, utilisable en pratique : un algorithme polynomial, mais pour un polynôme de degré élevé, disons 200, n'a aucune raison d'être utilisable en pratique. Cette assimilation est une commodité de langage dont les limites sont connues des professionnels du domaine ; dans une publication destinée à un public plus large, il aurait donc fallu faire la remarque que j'ai fait ci-dessus.

Je relève cependant plusieurs erreurs et insuffisances, et ce dès le deuxième paragraphe.

« Linear programming problems are NP, as the number of steps in the simplex method, […] grows exponentially with the size of the input. »

Faux. Vraiment très faux. La croissance au plus exponentielle du nombre de pas de calculs établit l'appartenance à la classe de complexité EXPTIME, et non à la classe NP. C'est une erreur courante chez ceux qui n'ont qu'une connaissance très superficielle de la complexité que d'assimiler classe NP et temps exponentiel, erreur inadmissible dans un ouvrage de référence. Ajoutons que, si l'on ignore si P et NP sont distincts, on sait cependant que P et EXPTIME le sont, par le théorème de la hiérarchie en temps déterministe. En revanche, distinguer NP et EXPTIME est également un problème ouvert.

Le fait que la programmation linéaire soit dans NP s'explique, si je ne m'abuse, par le fait que l'optimum du problème est atteint sur un sommet du polyèdre des solutions, et qu'un fois qu'on a sélectionné ce sommet par un choix nondéterministe, la vérification qu'il convient se fait par simple résolution de système d'équations linéaires, donc en temps polynomial.

« However, in 1979 Russian mathematician Leonid Khachian discovered a polynomial time algorithm—i.e., the number of computational steps grows as a power of the number of variables, rather than exponentially—thereby showing that linear programming problems are actually P. This discovery allowed the solution of formerly intractable problems. »

Deux erreurs. Premièrement, le fait que le nombre de pas d'un algorithme de programmation linéaire (ou, plus généralement, de calcul) croisse polynomialement en le nombre de variables n'implique nullement qu'il soit en temps polynomial. Il faut pour cela que la taille de chacun des nombres qu'il manipule croisse seulement polynomialement ; on obtient alors un algorithme « fortement polynomial ». Si on n'impose pas cette condition, on peut obtenir des algorithmes exponentiels : il suffit par exemple de considérer l'algorithme qui calcule 2^(2^n) en binaire à partir de n en binaire par élévations au carré successives. Tout algorithme fortement polynomial est polynomial, mais la réciproque n'est donc pas vraie. Qui plus est, si la méthode de l'ellipsoïde de Khachian est effectivement polynomiale, elle n'est pas fortement polynomiale, et c'est un problème ouvert de savoir s'il existe un algorithme fortement polynomial pour la programmation linéaire.

Deuxièmement, l'algorithme de l'ellipsoïde n'est pas utilisé pour résoudre des problèmes « précédemment intractables ». Il a un intérêt théorique, notamment de part sa possibilité de l'utiliser avec un oracle de séparation et pour des problèmes de programmation convexe hors de la programmation linéaire, mais personne ne s'en sert en pratique, à ma connaissance, car il est trop lent. Les algorithmes polynomiaux de programmation linéaire qui servent en pratique sont à ma connaissance basés sur des méthodes de points intérieurs.

« A problem is NP-hard if an algorithm for its solution can be modified to solve any NP problem »

C'est vrai dans les grandes lignes mais assez inexact (notamment: la réduction utilisée ne doit pas faire enfler le problème plus que polynomialement, et on n'a pas la possibilité de calculer la négation de la sortie de l'algorithme, ce qui permet de distinguer les classes NP et co-NP).

« In 1971 American computer scientist Stephen Cook proved that the satisfiability problem (a problem of assigning values to variables in a formula in Boolean algebra such that the statement is true) is NP-complete »

Je sais bien que Britannica est américaine, mais il aurait fallu également citer le scientifique soviétique Leonid Levin, qui avait obtenu indépendamment le même résultat à peu près au même moment, qu'on appelle donc souvent théorème de Cook-Levin.

« Such a discovery would prove that P = NP = NP-complete and revolutionize many fields in computer science and mathematics. »

Peut-être aurait-il fallu noter que la conjecture généralement adoptée par les scientifiques du domaine est que P et NP sont distincts...

Bref, si un article pareil s'était trouvé sur Wikipédia, et disons non pas en informatique théorique mais en histoire, nul doute qu'il aurait pu être relevé par Middlebury College ou par WikiGrill pour expliquer que Wikipédia est de mauvaise qualité.

Comment a-t-il pu se retrouver dans une publication aussi prestigieuse que la Britannica ? Son auteur ne m'est pas inconnu : c'est l'employé de l'encyclopédie qui avait également rédigé l'entrée biographique sur mon collègue Joseph Sifakis, que j'avais fait rectifier sur des points de détail. Il est chargé du secteur mathématiques et informatique, mais n'est titulaire que d'un master et non d'un doctorat. Zéro publication dans MathSciNet, zéro dans DBLP : il n'a pas fait de recherche publiable dans ces domaines : il ne s'agit donc pas d'un des « experts » ou « grandes signatures » tant évoqués quand on parle de Britannica ou d'Universalis. Qui plus est, le fait d'être diplômé de mathématiques et d'avoir fait de la recherche, disons, sur les équations aux dérivées partielles, ne transformerait pas ipso facto en connaisseur d'algorithmique et de théorie de la complexité, et vice-versa...

Le fait que des articles de Britannica soient maintenant écrits non pas par des autorités du domaine, mais par des employés éditoriaux, est d'ailleurs signalé par le président de Britannica, qui y voit un indice de meilleure réactivité :

« Many articles are also written by staff editors. We have only accepted 33% of user submissions and they helped enlarge the database, made it more accurate, and pointed out different ways to treat a topic and areas where we needed to expand knowledge. Articles by experts can become outdated, so we work with them to update the content. It’s really a constant dialog between us and the original contributor. That's very different than the way we operated before and allows us to create a better product. »

Signalons toutefois que le problème P vs NP n'est pas un problème scientifique récent, vu qu'il date de 1970. Son seul aspect récent est son inclusion sur la liste des problèmes du millénaire, en l'an 2000. Il y aurait donc eu amplement le temps de faire rédiger un article par un spécialiste.

Mon propos n'est évidemment pas de dénigrer l'Encyclopædia Britannica, qui propose, comme je l'ai dit, des entrées remarquables. Je veux simplement mettre en garde contre un raisonnement simpliste qui voudrait que les entrées de cette encyclopédie soient toutes écrites par des experts, tandis que celles de Wikipédia le seraient par des lycéens, des amateurs, ou des étudiants immatures. Il est ainsi pour moi clair que les articles sur la complexité sur la Wikipédia en anglais ont été écrits, dans l'ensemble, par des personnes qui savaient ce qu'elles disaient, en tout cas plus que le rédacteur de l'article P vs NP sur la Britannica.La réalité est bien plus complexe.