The answer is bigger than the question

A strip of twelve stamps is described by twelve numbers. It folds flat in 146,376 ways.

That is a mismatch of a particular kind and it has a name. The input is twelve numbers; the output is a hundred and forty-six thousand objects. Whatever algorithm is used, and however clever it is, it cannot finish faster than it can write down its own answer. There is no speedup available, no data structure that helps, and no conjecture in complexity theory whose resolution would change it.

This is a second kind of hardness, and it is worth separating carefully from the first, because folding has both and they behave completely differently.

Two hardnesses #

NP-hardness says: the answer is small — one bit — and finding it may take exponentially long. The output is a yes or a no; all the cost is in the search. Flat-foldability of a general crease pattern is this kind.

Output-sensitive hardness says: the answer is exponentially large, so producing it takes exponentially long, and there is nothing pathological about that. The search may be entirely straightforward. Listing the ways a strip folds is this kind.

The difference matters because the two suggest completely different responses. Against NP-hardness the useful moves are restriction, approximation and heuristics — narrow the family, accept an answer that is nearly right, or hope the instances are kind. Against output-sensitive hardness none of those apply, because nothing is wrong. The only useful move is to ask a different question: a count instead of a list, a sample instead of a count, a property of the set instead of the set.

The right way to measure it #

If an algorithm’s answer is enormous, judging it by input size alone is a category error, and the fix is straightforward once stated: measure the cost against the size of the output as well.

An enumeration algorithm is called output-polynomial when its total time is polynomial in the input and the output together. It is polynomial-delay when the gap between one answer and the next is polynomial in the input alone — a much stronger property, and the one that makes an enumeration usable, because it means the answers stream out at a steady rate rather than after an unpredictable wait.

Judged this way, some algorithms that look catastrophic are perfectly good. An enumerator that emits 146,376 foldings in forty seconds is emitting one every 270 microseconds. That is not a slow algorithm. That is a fast algorithm with a great deal to say.

Judged the other way, it is a forty-second computation on twelve numbers of input, which sounds like a disaster and is not.

What the enumerator here does #

The map-folding counter used here places cells one at a time and rejects a placement as soon as two folds interleave. It never builds a folding and then discards it; it never revisits a rejected prefix. That is the good structure — a backtracking search whose pruning happens at the earliest possible moment.

And it is still forty seconds at twelve stamps and fifty-four at a three-by-four map, because the answer is what the answer is.

The pruning does buy something real, and it is worth quantifying rather than assuming. Without it the search would place twelve cells in every order — twelve factorial, 479 million — and check each. With it, the search visits a few hundred thousand states to find 146,376 answers. So the pruning takes the cost from hopeless to proportional to the answer, which is the best any enumeration can do.

Reaching output-proportional cost is the finish line, not a stepping stone toward something better. There is nothing after it.

The same shape appears wherever this site enumerates. The assignment census tests every mountain-and-valley string against the local conditions, and the conditions prune early and hard — but what survives is exponential, so the enumeration costs what the survivors cost. The machine census decides 2ⁿ assignments one at a time, and the decision is cheap while the 2ⁿ is not. In every case the pruning is doing its job and the job has a floor.

What an exponential answer does to a build #

The abstract point has a concrete consequence in this repository, and it shaped the figures on this page more than any editorial decision did.

A figure generator on this site runs while the page is built, and a build that takes an hour is a build nobody runs. So every enumerator has a limit compiled into it, and each limit is a statement about where the answer stops fitting: eight segments for stacking search, ten creases for the machine census, nine stamps for the growth ratio drawn on this page.

Those numbers are small, and it is worth being clear that they are not small because the code is slow. They are small because 9! is 362,880 and 10! is 3,628,800, and one order of magnitude of input buys an order of magnitude of everybody’s afternoon. A ceiling written into an enumerator is the output-sensitive barrier arriving as a line of source code.

The one place this site deliberately pays the price is foldcheck, which is a gate rather than a build and can afford four seconds to verify the eleventh stamp number. The twelfth, at forty seconds, is quoted with its measurement and not recomputed — which is stated on the figure that quotes it, because a chart that quietly ends at the last cheap point is a chart about this machine rather than about the subject.

What the growth rate does to a ceiling #

The ceilings compiled into these enumerators look like arbitrary numbers, and they are not. Each one is the place where a fixed multiplier crosses a budget, and the multiplier is the same one the sequence is climbing toward.

The stamp numbers grow by roughly a factor of three and a fifth per stamp — 2, 3, 2.67, 3.13, 2.88, 3.21, 3.01, 3.26, 3.10, 3.29 as the terms go up, oscillating from either side of something a little above three. If the enumerator’s cost is proportional to its output, and here it very nearly is, then each extra stamp multiplies the computation by that same factor.

That turns a ceiling into arithmetic. Forty seconds at twelve stamps is a little over two minutes at thirteen, seven at fourteen, twenty-two at fifteen, an hour and a quarter at sixteen. Three more stamps than the table holds is an afternoon; six more is a fortnight.

A ceiling is therefore not a threshold that better code would move. Doubling the enumerator’s speed buys two-thirds of one extra stamp, and every plausible engineering gain lands somewhere in that range. The table ends where it ends because a constant is being raised to a power, and constants of that kind are not negotiated with.

A ceiling on counting is not a ceiling on drawing #

The two notions from the section above have a consequence that is easy to miss and worth stating, because it decides what a page can show.

An enumerator with polynomial delay emits its answers as it finds them, at a steady rate, so it can be stopped. Asking for the first hundred foldings of a fifteen-stamp strip costs a hundred delays and no more, whatever the total is. An enumerator that is merely output-polynomial may do all its work before it says anything, and stopping it early buys nothing at all.

The backtracking search here is the first kind. It reaches a complete placement, reports it, and backtracks — so a partial run is a partial answer rather than nothing.

So the barrier is on counting, not on producing. A count needs every member of the set, and needing every member is what makes the cost the size of the set. A drawing of a few needs a few. That is why the ceilings sit where they do: every one of them guards a figure that reports a total, and a figure that showed a handful of foldings from an enormous set could have been drawn at any size at all.

Where the table stops, and why that is honest #

The map-folding table has nine entries. It is tempting to read that as a subject that has not been worked on, and the reading is exactly backwards.

The table stops where exhaustive search stops, and exhaustive search stops where the answers become too numerous to produce. The next square case after three by three is four by four, whose answer is 300,608 — computed once, by somebody with time — and the one after that is not known. Not “not published”: not known, because nobody has run a computation long enough, and because there is no method that avoids running one.

So the shortness of the table is the result. A subject whose entire knowledge of a question is nine integers, every one of them obtained by brute force, is a subject where the output-sensitive barrier is the binding one — and what the ratio between those integers is doing is the only structural handle anybody has on it.

Counting without listing #

The obvious escape is to count without listing, and it is worth being precise about when that works, because it does work elsewhere and it does not work here.

Counting without listing is possible when the objects have structure a recurrence can exploit. The number of ways to triangulate a polygon is a Catalan number and nobody enumerates triangulations to find it; the count comes from a recurrence with a closed form. The number of binary trees, the number of lattice paths, the number of matchings in a path graph — all counted without being listed, all by finding a decomposition where a large problem’s answer is built from small problems’ answers.

Map folding has no such decomposition, and the reason is the same reason the two-dimensional problem is a different problem from the strip: a folding’s legality is a condition on pairs of folds that may be arbitrarily far apart in the map, so cutting the map in half does not cut the problem in half. The left half’s foldings and the right half’s foldings do not combine into the whole map’s foldings in any way anybody has found.

Absence of a recurrence is not a theorem that none exists. No lower bound says map folding cannot be counted efficiently. What exists is sixty years of people looking, which is evidence of a weaker and more familiar sort.

The one-dimensional case, where a recurrence nearly works #

The strip is the case where this is most tantalising, because the strip has structure the sheet lacks.

Overlaps on a line form a chain, and the non-crossing conditions are conditions on nested intervals. That is exactly the shape of structure that yields Catalan-like recurrences everywhere else in combinatorics. And the stamp-folding numbers — 1, 2, 6, 16, 50, 144, 462, 1392 — begin plausibly enough that a reader who has met Catalan numbers will start checking, and will stop at 16, which is not 14.

The sequence has no known formula. It has no known recurrence. It is in the literature as a list of values with an asymptotic growth rate that is conjectured rather than proved. For a sequence this small, this old and this structured, that is remarkable, and it is the strongest evidence available that the difficulty here is real rather than a failure of attention.

What the figures cannot do #

Every figure in this essay reports numbers rather than drawing objects, and that is forced rather than chosen.

An essay about outputs that are exponentially large cannot show the outputs. Sixty foldings of a two-by-three map is already beyond what a page holds legibly; 1,368 is not a picture. So the figures draw counts, ratios and tables — which is a real loss, because a count is a claim a reader has to trust rather than check.

The compensation is that every count here was computed by this repository and checked against a published value where one exists. The map counter agrees with Lunnon on all eleven cases he published; the strip counter agrees with the stamp-folding sequence on the first ten terms. Neither of those agreements is guaranteed by anything — two different enumeration rules can both be self-consistent and both wrong — and the checks are in foldcheck rather than in a comment.

The other thing no figure here can show is the shape of the answer set. All 146,376 foldings of a twelve-stamp strip are equally legal and there is no drawing that conveys how they differ. Somewhere in that set there are foldings a person would call obviously different and foldings a person would struggle to tell apart, and the enumerator has no opinion about which is which.

Sampling, which is the move that remains #

If listing is out and counting is out, one thing is still available and it is worth naming because it is what the rest of mathematics does in this situation: sample.

A uniformly random flat folding of a large map would answer questions no enumeration can reach — how many layers sit over a typical point, how the layer depth is distributed, whether a randomly chosen folding looks anything like the ones people make. None of those needs the full list, and all of them are the kind of question a manufacturer or a materials scientist would actually ask.

Sampling uniformly from a set nobody can count is its own difficulty, and it is a well-studied one: the standard approach is a random walk on the set of objects that mixes to the uniform distribution, and proving that such a walk mixes quickly is usually harder than the counting problem it was meant to avoid. This repository does not do it, and the reason is worth stating plainly — a walk on foldings would need a local move that preserves legality, and finding one is the same difficulty as everything else on this page.

What this does mean is that the shortness of the map-folding table is not evidence that nothing can be said about large maps. It is evidence that nothing can be enumerated about them, and those are different, in exactly the way this whole ladder has been insisting.

The idealisation, named #

Counting distinct foldings assumes an answer to a question the counting hides: when are two folded states the same?

The enumerator here counts layer orderings. Two orderings that differ only in the relative position of layers that never overlap are counted twice, and a folder would call them one object, because nothing about the paper distinguishes them. Turning the whole model over is likewise counted as a distinct state by the raw permutation search, which is why the machine simulator checks a stacking and its reverse before accepting it.

Different conventions give different numbers, and the published sequences use a particular one. That is why the checks in foldcheck matter beyond confirming arithmetic: agreeing with Lunnon’s counts is evidence that this repository’s notion of “distinct” is his, which no amount of internal consistency would establish.

Who worked this out, and when #

W. F. Lunnon computed the map-folding counts in 1968 and 1971, on machines with a small fraction of the memory in a phone, and his values are the ones every later table checks against. The stamp-folding sequence is older still as a curiosity and its terms have been extended by brute force ever since.

The framing — that enumeration algorithms should be measured against their output — is due to David Johnson, Mihalis Yannakakis and Christos Papadimitriou, who in 1988 set out output-polynomial and polynomial-delay as the right notions. That work was about graphs and had nothing to do with paper; it is the vocabulary this essay borrows, and it is what makes it possible to say that a forty-second computation on twelve numbers is not a failure.

Where the ladder goes next #

Three rungs have separated the questions, located the hardness and named the second kind. What is left is the one structural fact anybody has about the stamp numbers, and it is a ratio: the terms are climbing toward something, the something looks like a constant somewhere above three, and whether the limit exists at all is open.