Origami & Folding
what one sheet can do
Concept

Worst-case analysis — where it appears

The hardest instance a problem admits, which is what a hardness result is about. It says nothing about any particular pattern, because the instances a reduction constructs are engineered rather than typical.

Named by 13 essays across 3 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

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 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.

complexity · Hardness of folding 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.

complexity · Hardness of folding the bar is the share of random drawings with at least one crossing in them2 segments23.1%0.23 crossings on average3 segments51.2%0.69 crossings on average4 segments73.5%1.36 crossings on average6 segments95.2%3.48 crossings on average8 segments99.4%6.53 crossings on average12 segments100.0%15.30 crossings on average20 segments100.0%43.76 crossings on averageevery crease pattern in this collection has none, and none of them was drawn at random

Drawn by the same hand

Two straight segments dropped on a square cross about 23% of the time; four of them cross 74% of the time; twelve cross with certainty, about fifteen times over. Every crease pattern in this collection's four test populations has none — not because the checkers were catching them, but because the same rules that drew the patterns were incapable of producing one, and nothing looked until a construction finally did.

complexity · Typical instances the bar is the middle run of a hundred and twentysame pattern, same code — only the order the letters are tried in differsthe square patch2725 at best · 27 at the middle · 36 at worstthe elongated patch3432 at best · 34 at the middle · 39 at worstthe hexagonal patch4339 at best · 43 at the middle · 51 at worstthe triangular patch4539 at best · 45 at the middle · 53 at worstthe rhombille patch16684 at best · 166 at the middle · 48 of 120 unfinished at 20000an unfinished run is left out of the middle rather than counted as its budget

Four easy patches and one that is not

Run the same search a hundred and twenty times on each of five tessellation patches, changing nothing but the order the letters are tried in. Four of them answer in between twenty-five and fifty-three steps every single time. The fifth answers in eighty-four steps at best, a hundred and sixty-six in the middle, and does not answer at all in forty-eight runs of the hundred and twenty.

tessellation · Twists 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.

complexity · Hardness of 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 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

The tail was named somewhere else

The search for a mountain-valley labelling of a tessellation patch costs eighty-four steps at best and does not finish at all two runs in five, and the cure is to stop and start again rather than to wait. None of that was discovered here. The distribution was described in the study of satisfiability solvers in the nineteen-nineties, the restart arithmetic is older still, and what a crease pattern contributes is one more instance.

history · Rediscovery heavier means the crease lies on more independent circuits157 panels, 282 arcs, circuit rank 126; circuits run from 4 to 26 arcs

Which choice the cost lives in

A backtracking search takes two decisions at every step — which thing to decide, and what to decide about it. The literature is almost entirely about the first. On these crease patterns the whole of the cost was in the second, and the structural improvement everybody reaches for first makes matters worse on fifty-two patterns out of eighty-seven.

complexity · Search order 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.

complexity · Hardness of folding the bar is what the whole job costs in expectation, in nodeson the rhombille patch, over the same 120 measured runs as the fixed cutoffsbest fixed, 100512chosen after seeing the runsunit 132226.30 times the best fixedunit 228545.58 times the best fixedunit 525424.97 times the best fixedunit 1021524.20 times the best fixedunit 2017623.44 times the best fixedunit 508481.66 times the best fixedunit 1005511.08 times the best fixedunit 2006381.25 times the best fixeda unit of one assumes nothing about the runs; every larger unit is a guess at their scale

What the hindsight was worth

The best restart cutoff for the one tessellation search with a heavy tail was read off a hundred and twenty measured runs, which nobody running the search could have done in advance. The universal schedule needs no such knowledge, and on the same runs it costs 3,222 nodes in expectation against 512 for the cutoff chosen by looking — a factor of 6.3, which is close to the base-two logarithm of that cutoff, as the theory of the schedule says it should be. A larger unit brings the schedule within a few per cent of the hindsight, and choosing the unit is choosing the scale the schedule was meant not to need.

history · Rediscovery the expected cost of the whole job under rules that learn from their own failures, in nodeson the rhombille patch, over the same 120 measured runs; the dark bar borrows its unit from other patchesbest fixed, 100512chosen after seeing the runsdouble after every failure1820at least 3.56 times the best fixeddouble after every failure, from sixteen1805at least 3.53 times the best fixedgrow by half after each failure1204at least 2.35 times the best fixeduniversal, unit of one32226.30 times the best fixeduniversal, unit from other patches8721.70 times the best fixeda rule that reads only its own failures cannot beat the best fixed cutoff, and cannot know which that is

A failure teaches a schedule nothing

The universal restart schedule costs 6.3 times the cutoff chosen by hindsight on the one folding search with a heavy tail, and the obvious repair is a schedule that learns its scale from the attempts it has already made. It cannot. A failed attempt costs exactly its cutoff and reports only that the run needed more, so every rule that chooses the next cutoff from its own failures writes down the same list whatever happens — a fixed schedule in disguise. On the measured runs, doubling after every failure costs at least 3.6 times the hindsight, and growing by half at least 2.4. What does come near is information from outside the run: the universal schedule given the longest search on four other patches as its unit costs 1.7 times the hindsight. The field that supplied the schedule reached the same conclusion, and answered it by watching runs from the inside.

history · Rediscovery

Named alongside it

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

Search costSearchDecision procedureMeasurementRestartThe decision problemHeuristicRandomised algorithmRediscoveryTypical instancesCrossingGenericity

All concepts