of possible interest:

Noijima, T, "Origami Modeling of Functional Structures based on  
Organic Patterns"
http://impact.kuaero.kyoto-u.ac.jp/pdf/Origami.pdf

also discussed in Nature Vol. 448 26 July 2007 p 419.  Apparently the  
basic origami problem (given a diagram of fold lines, can the paper  
be folded without introducing creases?) is equivalent to 3-SAT.

-Dave