---

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.

---