---

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 wich is known to be NP-complete. They give a sample of that kind of origami by converting binary variables into folds. With the help of Robin Fercoq, i have tried to experiment and produce the most difficult possible crease-pattern. We estimate that this origami is at least impossible to fold by a human folder.

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 piece of simple origami (below) which allows to circulate binary information (mountain/valley creases) with more or less of constraint. All gadgets are connected to each others by wires. A wire is represented by two parallel creases. Each gadget locally is easy to fold flat. But the entire crease-pattern is very hard to fold because each crease assignment depends to the others.

---