Je savais déjà qu'Universalis avait un seul et unique article sur l'algorithmique (écrit par mon talentueux collègue Philippe Flajolet), mais j'osais espérer qu'ils avaient au moins un article évoquant les problèmes de théorie de la complexité, ne serait-ce que pour la raison que le problème P ⊊ NP est un des « problèmes du millénaire en mathématiques », d'où un certaine mise en lumière médiatique.

Curieusement, on ne trouve strictement rien sur le sujet ; le mot « NP-complet » n'apparaît nulle part. C'est d'autant plus curieux que l'on trouve des articles sur la théorie des fonctions récursives, autrement dit la théorie de la calculabilité, et que le cours de complexité suit habituellement celui de calculabilité dans les cursus universitaires.

Pourquoi une telle omission ? Une première interprétation est que la théorie de la récursivité est la version mathématique de la calculabilité, tandis que l'on classe plutôt la complexité en informatique théorique, et que les mathématiques seraient jugées naturellement plus « nobles » et dignes de figurer dans l'encyclopédie que l'informatique théorique.

Une autre interprétation est plus inquiétante. La théorie de la complexité a pris son essor après la démonstration par Stephen Cook que le problème SAT était NP-complet, en 1971. Or, Universalis a été fondée vers la fin des années 1960, et la plupart des articles ont dû être écrits fin des années 1960, début des années 1970. Autrement dit, l'omission serait due à un retard de 30 ans sur l'état de la science.

Dans les deux cas, je trouve cela quelque peu inquiétant à l'égard d'un ouvrage que l'on couvre habituellement de louanges.