Origami & Folding
what one sheet can do
Series

Hardness of folding — the series

13 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · complexity
  2. 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.

    part 2 · complexity
  3. mapflat foldingsand what it took2 × 284 cells, computed here2 × 3606 cells, computed here2 × 43208 cells, computed here3 × 31,3689 cells, computed here2 × 51,9800.6 s3 × 415,55254 s4 × 4300,608not reached herethe 1 × n case is the strip, and it is the only row of this table with a fast methodnobody has a formula for any entry, and nobody has proved there is none

    The answer is bigger than the question

    A twelve-square strip of stamps is twelve numbers of input and 146,376 objects of output. No algorithm writes that faster than it can be written, so 'efficient' has to be measured against the answer rather than against the question — and in folding that is the normal case.

    part 3 · complexity
  4. 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.

    part 4 · complexity
  5. every condition holds here6 creases4 creasesevery condition holds at the vertex on the paper — and one crimp later the smallest sector has the same letter on both sidesthe four conditions all hold · a stacking does not exist

    A short reason to say no

    When a folding question comes back yes it brings an object anybody can check. When it comes back no it usually brings nothing but the assurance that a search looked everywhere. At one vertex that is false: a refusal comes with a witness one or two steps long, out of a search space of a hundred and twelve, and the witness is a vertex the crease pattern does not contain.

    part 5 · complexity
  6. the four cheap tests are polynomial in the drawing; the fifth is notreading across a row is one pattern put to all fivecrease pairsverticespanelscreasessearch nodesthe square twist6649127,565the Miura fold703152438refusedthe waterbomb sheet2,850255276refusedthe Yoshimura3,655226586refuseda square patch3,486364984refuseda rhombille patch39,621126157282refuseda refused search is a pattern about which the expensive test says nothing at all, at full price

    The cost is in the coincidences

    How big an instance is, is what a hardness statement is about, and it is the weaker predictor of what deciding one costs. Hold the degree fixed and vary only how many of a vertex's sectors are equal: the work of deciding it rises by a factor of nearly three, against a factor of two for doubling the number of creases. The expensive instances are the ones a designer draws on a grid.

    part 6 · complexity
  7. the bar is how many of the 33 patterns each refusal is the first to catchtwo creases cross5one sweep over pairs of creasesa vertex condition fails0one pass over the verticesthe panels do not place0one walk over the panelsthe letters force a loop0one pass over the crease listno ordering exists6every ordering of the panels22 of the 33 are refused by none of these and are folded, undecided, or waiting on a search too large to run

    The order the refusals come in

    This collection can say no to a crease pattern in five ways, and they cost wildly different amounts: a sweep over pairs of creases, a pass over the vertices, a walk over the panels, a pass over the crease list, and an enumeration of every ordering of the panels. Run all five over the thirty-three patterns in the four test populations and the cheapest refuses five, the most expensive refuses six, and the three in between refuse nothing at all.

    part 7 · complexity
  8. the bar is how many of the 38 patterns each refusal is the first to catchtwo creases cross5one sweep over pairs of creasesa vertex condition fails0one pass over the verticesthe panels do not place0one walk over the panelsthe letters force a loop1one pass over the crease listno ordering exists6every ordering of the panels26 of the 38 are refused by none of these and are folded, undecided, or waiting on a search too large to run

    The refusal that reads the list once

    There are five ways of saying no to a crease pattern here, and their costs are two hundred and eighty-two, a hundred and twenty-six, a hundred and fifty-seven, thirty-nine thousand six hundred and twenty-one — and a search that is refused outright. On the largest patch the four cheap tests together do less work than one of them looks like it should, and the fifth cannot be started. A refusal that reads the crease list once is the only kind that scales.

    part 8 · complexity
  9. the bar is what the whole job costs if every attempt is stopped thereon the rhombille patch, read off 120 measured runsstop at 10051219% of runs finish by thenstop at 20053033% of runs finish by thenstop at 500105435% of runs finish by thenstop at 1000162442% of runs finish by thenstop at 2000263847% of runs finish by thenstop at 5000569749% of runs finish by thenstop at 100001060450% of runs finish by thenstop at 200001629160% of runs finish by thena run that never finished counts as above every cutoff, so the tail is read conservatively

    Stopping is cheaper than finishing

    A search whose cost varies by a factor of two hundred with nothing but the order of its guesses should not be waited out. Give up after a hundred steps, reseed and start again, and the whole job costs five hundred and twelve steps in expectation; run each attempt to twenty thousand and it costs sixteen thousand two hundred and ninety-one. Patience is thirty-two times more expensive than impatience.

    part 9 · complexity
  10. the curve is stop-and-restart; the rule is a constant letter order1001e+31e+41001e+31e+4563 at a cutoff of 10080 nodes, deterministic, nothing to restartexpected nodes in totalcutoff, in nodes

    Restarting what cannot be restarted

    Stopping a search early and starting it again with a fresh seed costs five hundred and twelve steps in expectation against sixteen thousand for patience. Every number in that is right. The distribution it is right about was made by the search's own coin, and taking the coin out costs eighty — with nothing left to reseed.

    part 10 · complexity
  11. proving the glued square cell has no lettering1×1, 4 panels3proved there is none · the other test found one in 32×2, 16 panels35proved there is none · the other test found one in 93×3, 36 panels3,455proved there is none · the other test found one in 6254×4, 64 panels200,000still running at the budgeta bar at the budget is a search still running, not a proof

    The cost of proving something false

    A search closing its whole tree is the strongest result this collection can produce, and on a glued tessellation it produces one that is wrong. What it costs to reach is three steps at one period, thirty-five at four, three thousand four hundred and fifty-five at nine, and more than two hundred thousand at sixteen — growing far faster than the cost of finding the lettering it says does not exist.

    part 11 · complexity
  12. 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.

    part 12 · complexity
  13. the same 2×2 glued cell, searched under two rulesa cycle is a contradictiona cycle whose steps add to zero isand what the loops dothe square gridnothing, in 359 nodesevery loop travels (2 directions)the triangular gridnothing, in 12,143455 nodesevery loop travels (2 directions)the honeycombnothing, in 9,6191,043 nodesevery loop travels (3 directions)the elongated triangular tilingnothing, in 9,123162 nodesevery loop travels (5 directions)the rhombille tilingunfinished at 200,000unfinished at 200,000—“nothing, in n” is an exhausted search: a proof that the pattern has no consistent lettering, which is false

    The cost of asking the wrong sheet

    A test written for a sheet with an edge, run on a sheet without one, does not fail. It exhausts — proving, at three, thirty-five and three thousand four hundred and fifty-five nodes, that no lettering exists — and the letterings it proved impossible fold, on the collection's own machinery, at every size they were tried at.

    part 13 · complexity

All series