Origami & Folding
what one sheet can do
Concept

The Bern–Hayes reduction — where it appears

The 1996 result that deciding whether a crease pattern folds flat is NP-hard. The hardness lives in the layer ordering rather than in the angles, which is why the local conditions can be complete and the problem still hard.

Named by 2 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

Named alongside it

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

NP-hardReductionAssignmentDecidabilityThe decision problemLayer orderingThe machine modelThe taco-taco conditionWorst-case analysis

All concepts