En rédigeant quasi simultanément, en 1947-48, son article pionnier "Science and Complexity" et sa longue introduction à "Mathematical theory of communication" de C.E. Shannon, W. Weaver établissait une correspondance entre les concepts de complexité et d'information qui semble toujours riche de promesses. Les développements quasi parallèles de la cryptographie ont suggéré un troisième terme, la computation, pour la compréhension et l'instrumentation de cette correspondance complexe. Peut­on faire le point, quelque quarante ans plus tard alors que mathématiciens et informaticiens assurent avoir beaucoup progressé dans la dernière décennie ? C'est le projet de ce bref recueil qui collige six études de six spécialistes réputés (J. Traub, J. Hopfield, A. Yao, ete.).

Peut­on marier la "théorie de l'information" (C. Shannon) et la "théorie de la complexité computationnelle" ? Ne faut­il pas concevoir une "troisième théorie" qui distinguera l'information d'un message (Shannon) de l'"information" contenue dans un message (les "" importent !). J. Traub (dans un texte très accessible qui synthétise bien ses travaux sur le thème de la complexité computationnelle, formalise une distinction entre la complexité combinatoire (l'information est complète, exacte et disponible) et la complexité "basée sur l'information" ("Information­based" : l'information est partielle, disséminée et coûteuse) : Autrement dit, une complexité attachée au problème à résoudre et non à l'algorithme de résolution, complexité qui exprime "l'irréductible incertitude" des données de ce problème. (On disposait déjà d'une intéressante présentation de la thèse de J. Traub dans un chapitre de l'ouvrage de sa femme, Pamela McCorduck : "The Universal Machine" ­1985 ­ Mc Graw Hill : Voir Afcet­lnterfaees, nov. 1988, N° 73, pp. 34­35).

Enrichi par cet effort original de conceptualisation, le lecteur demeure cependant "insatisfait, du fait peut­étre des instabilités du vocabulaire... au moins d'un auteur à l'autre : la complexité dans la théorie de l'information n'est pas la théorie de la complexité informationnelle, qui n'est pas la théorie de l'information complexe (ou incertaine), qui n'est pas la théorie de l'information computationnelle, qui n'est pas la théorie de la complexité communicationnelle, etc. Difficulté bien compréhensible dans un domaine présumé complexe. Il me semble que la distinction proposée par J. Traub entre la complexité combinatoire (celle des algorithmes P ou NP ?) et la complexité "informationnelle" est féconde. Mais alors ne faut­il pas convenir que les "résultats" mathématiques effectivement disponibles aujourd'hui portent surtout sur la complexité algorithmique ou combinatoire (l'hyper complication donc ?) et peu sur la complexité "informationnelle"... celle précisément à laquelle s'attachent les recherches sur la modélisation de la complexité ? Il reste que "Complexity in information theory" est désormais une "entrée" importante dans les bibliographies des études en sciences de la complexité : au moins parce que ce livre permet de poser ce type de question.