Plier une feuille de papier pour en faire une girafe, une pivoine ou

un nénuphar. Il a fallu des siècles aux Japonais pour faire de ce passe-temps un art traditionnel: l'origami. Combien faudra-t-il de temps aux scientifiques pour inventer et résoudre les mathématiques de l'origami? L'un des problèmes les plus ardus (1), affirment ceux qui se sont attaqués à la question, est de prédire le patron d'un origami plié à plat ­ c'est-à-dire capable d'être pressé entre les pages d'un livre sans être déformé.

Pour les mathématiciens, cette question serait reliée aux problèmes dits «NP-complets», une classe de problèmes qui sont tels que, si l'un d'entre eux était résolu, ils le seraient tous. Or, au cours d'une réunion de mathématiciens qui s'est tenue à Baltimore (Etats-Unis) en janvier, Barry Hayes, un informaticien de Mountain View (Californie), a montré que ce problème de l'origami est équivalent au célèbre problème «dur» de l'informatique, le problème «not-all-true 3-SAT», en français «non-tous-vrais 3-SAT». «Ce qui n'a aucune utilité pratique», avoue le chercheur, puisqu'on ne sait pas résoudre plus facilement le problème «not-all-true 3-SAT», qu'un problème «NP-complet». Par ailleurs, Robert Lang, de la société SDL, de San Jose (Californie), a présenté une méthode pour fabriquer des origamis pliés à plat. Cette méthode permettrait notamment, à partir d'un carré de papier donné, de créer la figure la plus grande possible, à condition bien sûr qu'elle soit composée de formes rel