Technology Review: Blogs: arXiv blog: Origami Crease Pattern Design Proved NP-Hard

Technology Review: Blogs: arXiv blog: Origami Crease Pattern Design Proved NP-Hard: "The experts in this field have long suspected the process of turning a stick figure into a crease pattern is computationally intractable. Now Lang and co prove that this intuition is correct by showing that the process is NP-hard. So it is much harder to devise a crease pattern that produces a spider than it is to check that a given solution is correct (ie by folding it into a spider).

They've done this using the standard trick of showing that the problem of origami is equivalent to another problem that is already known to be NP-hard, in this case the problem of packing circles into a given space."