Origami & Folding
what one sheet can do
Concept

Decidability — where it appears

Whether a question can be settled by a procedure that always terminates. Flat-foldability is decidable and expensive; the interest is in what the cost is made of rather than in whether an answer exists.

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

6 interior vertices, every one satisfying both theoremswhat the local tests seeangles at each vertexassignment at each vertexwhat they cannot seewhether layer 3 passes through layer 7whether a flap has room to existwhether the order is consistent everywhereBern and Hayes, 1996: NP-hardso this pattern is checked, not proved

Local is not global

Every vertex can satisfy every condition and the sheet still not fold. Deciding whether a whole crease pattern folds flat is NP-hard, which means no figure will settle it and no algorithm will scale.

flat-folding · Flat-foldability MVMV123455 segments, 4 creases12345the stack, solvedassignmentsMVMVvalid stacks1decided byexhaustive searchover the orderingsthe folded positions come from the crease spacing; the assignment only decides which way each turn wraps

A strip is decidable

Take the same problem down one dimension and it stops being hard. The reason is not that strips are small — it is that overlaps on a line form a chain, and chains cannot contain the cycles that make the two-dimensional question intractable.

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

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

Named alongside it

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

Layer orderingNP-hardAssignmentThe Bern–Hayes reductionGlobal flat-foldabilityMap foldingOne-dimensional foldingReductionSelf-intersectionStamp foldingThe taco-taco conditionTractable restriction

All concepts