Origami & Folding
what one sheet can do
Concept

NP-hard — where it appears

At least as hard as the hardest problems in a class for which no efficient method is known. Deciding whether a crease pattern folds flat is one, which is a statement about the worst instances rather than about any pattern in particular.

Named by 9 essays across 3 fields — 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 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 6 creases, 7 segments, assignment MVMVMVDoes it fold flat?at most 5,040 orderings, and it may stop earlyyesas far as the first legal oneHow many ways?every one of them, because the last is as likely as the first15,040 orderingsWhat are they?the same search, paying a second time for what it keeps1 stackings, written out5,040 orderings, and the answer as wellCan a machine make it?a different search, over sequences of folds rather than over stackingsno1,275 statesthe four are not four difficulties of one problem — they are four problemsthe cost is work rather than time — a clock reading would differ on every build

Four questions about one sheet

Deciding, counting, listing and optimising are not four difficulties of one problem. They are four problems, and folding is the subject that proves it: a ruled map is trivial to decide and unsolved to count, while a general crease pattern is the other way round.

complexity · Hardness of folding 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 developableKawasakiMaekawabig-little-bigsectors that do not alternatefour creases turning the same waya small sector flanked by one lettera 4×3 Miura, every vertexthe last row passes all four tests at all 6 of its vertices, and passing is not a proofthe tests are conditions at a single vertex; whether the layers can be stacked is a condition on the whole sheetno arrangement of vertex tests decides that, which is what NP-hardness means when it is spelled out

What a checker cannot check

Every crease pattern on this site is run past four theorems before it is allowed onto a page, and passing all four proves nothing. The gap is not a bug to be closed: it is the NP-hardness result, arriving as a property of a hundred lines of code.

complexity · Flat-foldability discsfoundproved bestshort by20.292880.292890.00%30.254310.254330.01%40.250000.25000matched50.207050.207110.03%60.187580.187680.05%70.174360.174460.06%80.170220.170540.19%90.166670.16667matchedworst shortfall 0.19% of the radius, at 8 discsthe search never consults the published values, so the comparison measures the searchbeyond nine discs there is nothing to compare against, because nothing has been proved

Getting close instead of getting it right

When the best answer is out of reach the question stops being what it is and becomes how much is lost. For packing discs into a square the loss is measurable: a seeded search in this repository comes within a fifth of a percent of the best radius anybody has proved, and proves nothing.

complexity · Circle packing 0°30°60°90°0.250.400.550.700.85how much of the room between two vertices the twists takeno paper leftno assignment existstwist angleboth curves are measured rather than plotted from a formula

A no costs more than a yes

When a folding question comes back yes, it comes back with an object: a labelling, a stacking, a folded state that anybody can check in one pass. When it comes back no, it comes back with nothing but the assurance that a search looked everywhere — and that assurance is the first thing to break.

complexity · Hardness of folding the square twist, sieved three timesevery lettering4,0962 to the 12passes every vertex2566.3% of themletters are consistent2524 force a loop of panelshas a folded state80.20% of themthe bars are on one scale, so the last one is the size of the answer against the size of the question

The lettering that folds nowhere

The conditions at a vertex admit 256 letterings of the square twist. Eight of them have a folded state. The other 248 satisfy developability, Kawasaki, Maekawa and the big-little-big lemma at every vertex of the pattern and cannot be folded by anyone — and this site printed one of them for years, at true scale, with instructions to fold it first.

flat-folding · Flat-foldability the bar is the draws whose letters do not contradict themselvesa loop of panels is a proof that no flat folded state exists, and it costs one passone square twist39 of 409 panels · 12 creasesone hexagon twist40 of 4013 panels · 18 creasesa small square tiling24 of 4049 panels · 72 creasesthe square tiling7 of 4049 panels · 84 creasesthe patch a propagation returns first is not a draw and has no reason to be among these

The tiling the unit could not promise

Every twist on this site carries the same caveat: the unit is verified and the plane is not, because deciding a whole pattern is intractable. There is one thing about a whole pattern that costs a single pass over its crease list, and it says no. The square twist tiling was drawn with a lettering that contains a loop of twenty-eight panels, so the patch on this site had no flat folded state at all — and only seven of forty independent redraws avoid one.

tessellation · Twists

Named alongside it

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

Layer orderingThe decision problemNecessary conditionAssignmentThe Bern–Hayes reductionCrease assignmentDecidabilityFlat-foldabilityFolded stateOptimisationReductionThe taco-taco condition

All concepts