Origami & Folding
what one sheet can do
Concept

Reduction — where it appears

Turning one problem into another so that a solution to the second answers the first. Flat-foldability is proved hard by a reduction from satisfiability, and the patterns that reduction builds look nothing like origami.

Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.

state 0state 1V M M V — the same pattern in both2 valid stackings, found by enumerationwhat a junction would addthree wires meeting, with the layer orders forced to disagree —which is a clause, and which is where the reduction gets its powernot drawn and not verified: nothing here decides layer order in two dimensions

The gadgets that make it hard

Flat-foldability is NP-hard, and the proof is a construction rather than an obstruction: a machine for turning any satisfiability problem into a sheet of paper that folds exactly when the problem has an answer.

flat-folding · Flat-foldability state 0state 1V M M V — the same pattern in both2 valid stackings, found by enumerationwhat a junction would addthree wires meeting, with the layer orders forced to disagree —which is a clause, and which is where the reduction gets its powernot drawn and not verified: nothing here decides layer order in two dimensions

Hardness is about the worst one

Flat-foldability is NP-hard, and every crease pattern on this site is decided in under a second. Both are true, and holding them together is the difference between using the result and repeating it: hardness is a statement about the worst instance a family contains, and nobody folds the worst one.

complexity · Hardness of folding 4681012010203040sides of the polygoncreasescreases in the patternperpendicularsskeleton arcsa 12-sided outline needs 36 creases and one skeleton nodea convex outline is the cheap casea reflex corner splits the shrinking front, and this solver refuses those rather than guessing

What universality costs

The fold-and-cut theorem says any straight-line drawing can be flattened onto a single line. It says nothing about how much crease pattern that takes, and the amount is a measurable quantity — computed here by running the construction rather than by estimating it.

complexity · Flat-foldability

Named alongside it

The objects these essays reach for when they reach for this one.

The Bern–Hayes reductionNP-hardAssignmentCompletenessDecidabilityThe decision problemThe fold-and-cut theoremLayer orderingThe machine modelOutput-sensitive costStraight skeletonThe taco-taco condition

All concepts