Certains problèmes mathématiques que pose l'origami défient la puissance de calcul de nos ordinateurs actuels. Ce sont des problèmes classés NP-complet dans la théorie de la complexité. Plus la taille du problème est importante plus les chances de trouver une solution exacte dans un temps raisonnable sont réduites. En 1996, Marshall Bern et Barry Hayes, deux ingénieurs informaticiens du Xerox PARC (Palo Alto, Californie) ont démontré que certains dépliés d'origami font partie de cette classe de problème. Etant donné la marque des plis sur une feuille, dans quel sens faut-il la plier pour la mettre à plat ? Selon certaines conditions, des pliages sont de nature NP-complet. En revanche, personne n'a encore apporté la preuve que les problèmes NP-complet sont vraiment difficiles à résoudre. Autrement dit, prouver qu'une chose est réellement difficile est en soi réellement difficile...

Avec l'aide de mon ami Robin Fercoq, nous avons travaillé à la réalisation d'un déplié qui soit le plus difficile possible. Le déplié a été généré par ordinateur. Il s'agit d'un origami de type pavage (il se plie à plat). Constitué d'une matrice de 784 intersections (28 x 28), il ne contient en réalité que 4 gadgets différents. Un gadget est un pliage simple qui fait circuler l'information d'une manière plus ou moins contraignante d'un gadget à l'autre par le biais des rails (plis parallèles). L'information encodée est binaire puisqu'elle correspond au sens des plis (montagne ou vallée). Chaque gadget est facile à plier (voir ci-dessous). Ce qui rend cet origami difficile à plier, voire impossible bien qu'il soit pliable s'explique par le fait que tous les gadgets sont interdépendants. Le sens d'un pli en bas à gauche affecte celui d'un pli en haut à droite.

---