Origami & Folding
what one sheet can do
Concept

The decision problem — where it appears

A question whose answer is yes or no. Folding offers four different ones about the same sheet — does it fold, how many ways, list them, find the best — and their difficulties are not the same.

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

creases at 0.40, 0.50 — assignment MVflat1 layerno sequence of all-layers folds finishes this pattern — the search exhausted 5 states

The fold a machine can make

A theorem that says a folded state exists says nothing about getting there. A machine that folds every layer at once is stopped by a strip with two creases in it — one that folds flat perfectly well, and that a pair of hands folds in about four seconds.

complexity · Simple 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 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 32 × 32 gridevery crease on a grid line, or at 45°which is why a 64-grid design can be folded at allmountainvalley

Publishing the pattern instead of the sequence

A diagram sequence is one picture per step and a crease pattern is one picture. When designers began releasing patterns rather than diagrams, the cost of publishing a model fell by two orders of magnitude and the difficulty moved onto the reader — which is what made the complex era possible and what made most of it unfoldable.

history · Notation 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 1 × 4161 × 5501 × 61442 × 282 × 3602 × 43203 × 31,3684 × 4300,608filled — counted here, by exhaustive search over stacking ordersopen — Lunnon's published count, quoted rather than computed

Two directions that will not separate

A map has rows and columns, and a strip of stamps is a map with one row. The obvious hope is that the two-dimensional count is built from the one-dimensional one — fold the rows, then fold the columns. It is not: a two-by-three map folds 60 ways against a product of 12, and the discrepancy grows from a factor of two to a factor of thirty-eight over the counts anybody has.

complexity · Map folding the bar is how many patterns the population holdseach one sampled forty times and then searched, to see whether the two methods ever disagreethe printed patterns80 never lettered by 40 draws · all 8 settled by search · worst 60 nodestwist tessellations70 never lettered by 40 draws · all 7 settled by search · worst 19 nodesquadrilateral meshes60 never lettered by 40 draws · all 6 settled by search · worst 6 nodesfold-and-cut patterns70 never lettered by 40 draws · all 7 settled by search · worst 14 nodesthey never do here — the patterns that separate them are not in any of these four

Four populations with nothing to separate

This collection keeps four standing populations of crease patterns to test its machinery against. Twenty-eight patterns, sampled forty times each for a lettering that agrees with itself and then searched for one — and on every single member the two methods return the same verdict in the same breath. The patterns that separate them are in none of the four, and the reason they are not is what the populations are for.

complexity · Typical instances each cell is one patch, searched to a verdictgreen: a lettering exists · magenta: none exists, by exhaustion0.150.250.350.50.70.91.11.3turn angle, in radianssquare2626262626262626elongated1515323231313232hexagonal1515394545464545triangular1515393939373737the number in a cell is the nodes the search visited; 6 of 32 patches have no lettering at all

The order that proves nothing exists

Twelve crease patterns with no consistent lettering at all. Proving it takes fifteen steps under one rule and half a million under another — and on three of the twelve the two rules swap places, so neither is the good one. The cost of a negative is two to the power of how many free choices sit above the contradiction.

complexity · Search order which bands foldcreases across the strip123456nofoldsnofoldsnofoldsfoldsnofoldsnofoldsnocylinderMöbius bandthe gluing map of a cylinder is a slide and of a Möbius band a slide with a flipand a composition of k reflections turns the paper over exactly when k is odd

A proof in no nodes at all

A parity refuses a sheet before any search begins. It costs one addition, it is certain, and it says nothing about why — while a search that exhausts on the same sheet costs thousands of nodes and produces a proof of the same fact. Two proofs of one thing, and the cheap one is available only where somebody has noticed the invariant.

complexity · Hardness of folding

Named alongside it

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

NP-hardCertificateSearchWorst-case analysisAssignmentCombinatorial explosionCountingExhaustive searchLayer orderingThe machine modelMap foldingNecessary condition

All concepts