Toward NP-complete, 2008-05, Glassbox, Cité Internationale Universitaire, Paris


vers un déplié NP-complet
vers un déplié NP-complet
vers un déplié NP-complet
vers un déplié NP-complet

Some mathematical questions about origami represent a class of problem that are not solvable by our computers. Such problems are called NP-complete in computational complexity theory. Marshall Bern et Barry Hayes showed in 1996 that assigning mountain and valley folds in certain crease-patterns is equivalent to a 3SAT problem which is known to be NP-complete. But there is actually no proof that NP problems are really hard. So to prove something is really difficult is really difficult.

With the help of my friend Robin Fercoq, i have tried to experiment and produce the most difficult possible crease-pattern. The crease-pattern has been generated by a computer program. It is a tesselation origami. There is 784 intersections which are composed by only four different gadgets. A gadget is a simple part of the origami which allows connection of binary information (mountain/valley creases) with more or less constraints. All gadgets are connected to each others by wires (a kind of computer). A wire is represented by two parallel creases. Each gadget locally is easy to fold flat. But the entire crease-pattern is hard to fold because each crease assignment depends to the others.



gadget
gadget
gadget en transparence gadget
gadget
gadget en transparence gadget
gadget
gadget en transparence gadget
gadget
gadget en transparence

Thanks to Sonia Marques for the photos of the exhibition.