Hardness is about the worst one

Deciding whether a crease pattern folds flat is NP-hard. Every crease pattern on this site is decided, one way or another, in a fraction of a second, and none of them was chosen for being easy.

Those two sentences sit badly together until the first one is read carefully, and reading it carefully is most of what this essay is for. NP-hardness is a statement about a family of problems and its worst member. It says that no algorithm handles every instance quickly, unless a famous conjecture is false. It says nothing whatever about any particular sheet of paper.

What a reduction actually produces #

The Bern–Hayes construction takes a logical formula and builds a crease pattern that folds flat exactly when the formula is satisfiable. The gadgets are worth seeing in their own right; what matters here is what the assembled object looks like.

It looks like nothing anybody folds. Every part of it exists to carry or constrain a bit. The wires are strips whose only content is a two-state layer ordering. The junctions are places where three wires meet under a geometry chosen so that one combination is impossible. The whole sheet is laid out to route wires between clauses without crossings, which inflates it by a polynomial factor that a designer would consider ruinous.

A hardness proof needs the worst instances to exist, and it manufactures them. It does not claim they arise. It does not claim they resemble anything. The reduction is an argument that the problem’s difficulty is at least that of satisfiability, and the sheet it builds is the argument’s scaffolding rather than an example of the subject.

What the patterns anybody draws look like #

Now consider what a crease pattern from the design side looks like.

Periodic. Generated by a rule. Every vertex the same as every other, or one of two or three kinds. Angles drawn from a small set, often from a grid, often at multiples of 22.5° or 45°. Symmetries everywhere.

That is not an aesthetic observation. It is a structural one, and it is why the patterns in this collection are decided so quickly: a pattern with a generating rule has its foldability decided by the rule, once and for all, rather than instance by instance. The Miura folds because a single vertex folds and the tiling propagates it. A box-pleated base folds because the grid discipline that produced it is a discipline about foldability. A pattern that comes out of a circle packing folds because the packing was the certificate.

The hard instances are the unstructured ones, and the design process never produces unstructured ones, because a designer with no structure has no way to reason about what they are drawing either.

Measuring it rather than asserting it #

That argument is a story, and a story is worth a measurement.

Every crease pattern this site draws goes past the flat-foldability assertion before it is allowed onto a page. That check is four local conditions at every interior vertex and it costs time proportional to the number of creases. It is not a decision procedure and it never claims to be; it is a filter.

The interesting number is how often the filter is enough. Across the patterns in this repository — the Miura, the Yoshimura, twists at three sizes, the preliminary base, the fold-and-cut patterns, the box-pleated bases, the molecules — the filter passes them and a separate argument settles them: a generating rule, a verified single vertex, an explicit construction, or in one dimension an exhaustive stacking search. Not one of them needed anything like the effort the hardness result warns about.

That is not evidence that the result is wrong. It is evidence about which part of the instance space this subject lives in.

There is a sharper version of the same observation, and it concerns where the certificates come from. Every pattern in this repository is foldable for a reason that was available before the pattern was drawn — the vertex was solved, the packing was verified, the tiling was checked once. None of them was drawn first and interrogated afterwards. That is how design works and it is also, precisely, how the hard case is avoided: the hard case is the one where somebody hands over a finished sheet and asks.

The same asymmetry runs through the machine ladder. Asking whether a strip is reachable by a given machine is a search; knowing the sequence that made it is a certificate, and the certificate is cheap to check. A subject in which objects arrive with their construction attached is a subject that rarely meets its own worst case.

Where the difficulty would show up #

It is fair to ask what would happen if somebody did hand this site a hard instance. The answer is specific and it is not “the build would be slow”.

The exhaustive searches here have hard ceilings written into them. The layer enumerator refuses more than eight segments. The machine census refuses more than ten creases. The map counter will attempt anything and takes fifty-four seconds on a three-by-four map. Those limits are in the code as thrown errors rather than as slow paths, because a build that quietly takes an hour is worse than one that stops and says why.

So a hard instance would not produce a slow site. It would produce a refusal, and the refusal would be accurate: this machinery does not decide that, and it says so.

Hardness is about presentation #

The observation that every pattern here arrives with its construction attached is worth pushing one step further, because it identifies what the hard case actually is — and it is not a kind of pattern.

The decision problem is: here is a crease pattern; does it fold? The instance is a finished sheet with no provenance. Everything about how it came to exist has been discarded, and the solver has to recover from the drawing what the drawer knew.

That is the expensive presentation, and it is expensive whatever the pattern is. Hand the same Miura over as a drawing with no label and the solver has to search; hand it over as the tiling of this vertex, which folds and the answer is a lookup. Same object, same creases, same letters — and the difference in cost is the difference between a factorial search over sixty-five panels and reading one sentence.

So the hardness is a property of what is handed over rather than of what is drawn. The reduction’s sheets are hard because they are handed over stripped, and they are designed to be uninformative when stripped: every gadget’s structure exists to make the answer depend on a global combination rather than on anything a reader could see locally.

Which is a warning about how a subject publishes #

That reframing has a practical edge for a field that transmits its work as drawings.

A collection that keeps its constructions never meets its worst case. Every pattern in this repository is foldable for a reason recorded beside it — a solved vertex, a verified tiling, a checked packing — and the reason is the certificate, obtained free as a by-product of designing.

A collection that publishes finished sheets manufactures hard instances for its own readers. A crease pattern printed without its construction is exactly the stripped presentation the decision problem is about, and a reader who wants to know whether it folds is being asked the intractable question rather than the easy one. That is the same gap a notation leaves seen from the complexity side: what is not written down is not merely absent, it is the difference between a lookup and a search.

The practical rule is short and it costs nothing. Publish the rule, not only the drawing. A tessellation’s unit and its tiling, a base’s packing, a molecule’s polygon — each of them is a sentence, each is what made the pattern foldable, and each turns the reader’s problem from the hard one into the trivial one.

An instance is not hard, and this is not a quibble #

There is a sentence that gets written about NP-hard problems and that is simply ungrammatical, though it reads perfectly well: this instance is NP-hard.

No instance is NP-hard. NP-hardness is a property of a language — an infinite set of instances — and it says that recognising membership of that set is at least as difficult as recognising membership of any set in NP. Ask it of a single crease pattern and there is nothing for the definition to bite on: a single pattern either folds or does not, and an algorithm that answers correctly for that one pattern is a lookup table.

This matters more than it sounds, because it decides what a hardness result can be used for. It cannot be used to explain why a particular design was troublesome. It cannot be used to justify giving up on a particular sheet. What it can be used for is to rule out a class of ambitions: no local test will ever decide the general problem, no clever normal form will make the general problem polynomial, and any algorithm claiming to decide every crease pattern quickly is claiming something enormous about complexity theory and should be read in that light.

That last figure is worth reading against the grain. It is a table of small numbers about a problem that is famously intractable. Nothing about it is contradictory and nothing about it is informative about the intractability either. A benchmark on natural instances is a measurement of the benchmark.

The three ways the result gets misread #

Three misreadings, in increasing order of how often they appear in prose about this subject.

“Flat-foldability is undecidable.” It is not. It is decidable by exhaustive search over layer orderings, which always terminates. NP-hard means expensive in the worst case; undecidable means no algorithm at all, and the two are not neighbours.

“So there is no point looking for algorithms.” There is every point. The result rules out a fast algorithm for all instances. It says nothing about fast algorithms for grids, for periodic patterns, for one dimension, for patterns with bounded layer depth, or for any of the other restrictions that carve up the instance space — and the useful algorithms in this subject are all of that kind. A strip is decidable and its algorithm is not exponential; that result is not in tension with the hardness of the general problem, it is what the general result leaves room for.

“A pattern that passes the local checks probably folds.” This is the dangerous one, because it is a probability claim about a distribution nobody has defined. Probably under what measure? Over the patterns a designer draws, the local checks are nearly always enough — and that is a fact about designers. Over the patterns a reduction builds, they are never enough, by construction. There is no neutral distribution over crease patterns to be probable with respect to.

What the assignment census says #

There is one place where a quantitative statement about “most patterns” can be made honestly, because the family is finite and completely enumerated.

At one vertex the census is exact and the surviving fraction is small. As the pattern grows the fraction that survive falls and the number that survive rises, which is the shape that makes a filter useful and a decision procedure necessary — a strong filter leaving exponentially many candidates is still leaving exponentially many candidates.

The honest reading is that the local conditions are enormously effective per unit of work and that their effectiveness does not compound into a decision. Both halves are measurable and this site measures both.

What this does not license #

Having argued that hardness says little about the patterns anybody draws, it is important to say what that does not permit.

It does not permit asserting that a pattern folds because it looks like it should. The local conditions are necessary. The generating rule, where there is one, is what makes the pattern foldable, and the rule has to be checked — which is why the Yoshimura pattern on this site is built by a verified generator rather than drawn, after the drawn version turned out to put six mountains and no valleys at a degree-six vertex for three phases.

It does not permit treating the checker as a decision procedure. The blind spot is real and it has its own essay.

And it does not permit optimism about the two-dimensional questions this site avoids. Nothing here decides whether a general two-dimensional pattern folds; the machinery is local, the strips are one-dimensional, and every figure that could be read as claiming otherwise says so on its face.

The one place the worst case does arrive #

There is a family where the pessimistic reading is the correct one, and it is worth naming so the essay does not read as a general reassurance.

When the question is which of these exponentially many assignments has some property, and the property is not local, there is nothing for a filter to do and the search space is the cost. The censuses on this site are all of that shape, which is why every one of them carries a hard ceiling on the number of creases: two to the tenth is a thousand strips to decide, each decided by a search of its own, and the product is what stops the table.

This is the worst case arriving in an ordinary place. Nothing about an evenly creased strip is adversarial; it is the most regular pattern in the subject. The cost is in the question rather than in the paper, which is the theme of the whole ladder and the reason the two rungs sit next to each other.

The idealisation this argument rests on #

The whole essay compares two populations of crease patterns — the ones a reduction builds and the ones a designer draws — and treats them as though they were the only two.

There is at least a third and it is growing: patterns produced by a solver. When a computer packs circles, routes rivers and emits a crease pattern, the result has the structure the algorithm gave it and not necessarily the structure a human would have imposed. Those patterns are much less regular than a Miura and much more regular than a reduction’s output, and where they sit is not something this site has measured.

There is a fourth, more speculative: patterns produced by optimising something other than foldability — minimum thickness, minimum crease length, maximum stiffness. An optimiser pushed hard against a constraint tends to produce exactly the awkward, structureless configurations that hardness results are about, because the structure was what it was spending. That is a reason to expect the hard instances to become less exotic over time, and it is a prediction rather than a measurement.

Who said it, and when #

The general point — that a worst-case complexity result constrains algorithms rather than instances — is as old as complexity theory and belongs to nobody in particular. What folding adds is an unusually vivid version of it, because the gap between the hard instances and the natural ones is visible to the eye: a Miura and a Bern–Hayes sheet do not look like two members of the same family.

Marshall Bern and Barry Hayes published the reduction in 1996. It is worth noting what they claimed, which is narrower than what gets repeated: that the problem is NP-hard, that it stays hard when the assignment is given, and that the difficulty lies in the layer ordering. All three are statements about the problem. None is a statement about a sheet of paper.

Where the ladder goes next #

The word “efficient” has been used here as though its meaning were settled. For most of folding’s counting questions it is not, because the answer is exponentially larger than the question and an algorithm cannot be faster than its own output. That is a different kind of hardness from this one, it applies to problems that are not NP-hard at all, and it is the one that actually stops the map-folding table.