Four questions about one sheet

“How hard is flat-folding?” is not one question, and the habit of treating it as one is the source of most of the confusion in this corner of the subject. A crease pattern admits at least four distinct questions, and their answers are not ordered.

The four are worth naming precisely, because each has a standard name and the names get used interchangeably in prose where they are not interchangeable at all.

Decide. Does a flat folded state exist? Answer: yes or no.

Count. How many are there? Answer: a number.

List. What are they? Answer: an object for each one.

Optimise. Which is the best, for some measure — fewest layers over any point, least total crease length, most compact? Answer: one state and a proof that nothing beats it.

Every one of these has been asked of folding, and the answers arrange themselves in an order that has nothing to do with which question sounds harder.

The map, which is easy to decide and impossible to count #

A rectangular map ruled into m × n squares, every rule line a crease. Does it fold flat?

Yes. Always. Fold all the vertical lines into a strip, then fold the horizontal ones, and the result is a single square pile. There is no case analysis, no condition on the dimensions, and no interesting content in the question at all. Deciding is trivial.

How many ways does it fold?

Nobody knows. The counts are known for a handful of small cases, every one of them by exhaustive search, and there is no formula for any of them. The question is the oldest open problem in the subject, it was already old when Stanisław Ulam wrote it down, and the gap between it and the decision version is total: one is answered in a sentence and the other has resisted sixty years.

Same object. Same rule lines. The difficulty went from nothing to open by changing the verb.

The general pattern, which is the other way round #

Now take a crease pattern that is not a ruled grid — an arbitrary arrangement of creases on a sheet, with mountains and valleys assigned.

Does it fold flat? That is NP-hard, by the Bern–Hayes reduction from not-all-equal satisfiability, and hardness survives even when the assignment is given for free. The decision question, the trivial one for maps, is the hard one here.

Counting is at least as hard, since a count of zero answers the decision. So the order has flipped: for maps, decide is easy and count is open; for general patterns, decide is already hard and everything above it inherits.

The lesson is not that folding is hard. It is that difficulty is a property of the pair — this question about this family — and that swapping either half changes the answer without warning. Restricting to ruled maps made deciding trivial and left counting open. Asking for a count instead of a yes made a trivial problem impossible. Neither move is monotone.

What counting costs when the count is the answer #

There is a specific reason counting is so often harder than deciding, and it is visible in the first figure’s second column.

A decision procedure may stop. The instant it finds one legal stacking it is finished, and a search that can stop early is a search that spends its effort on the easy instances rather than on the hard ones. That is why the first row of the figure reads at most the full number of orderings while the second reads all of them: the decision’s cost is a ceiling and the count’s is a total.

A counting procedure may never stop early. It has to examine everything, because the last arrangement tested is as likely to be legal as the first. So counting costs the whole search space, always, whatever the instance looks like.

The gap between the top line and the bottom line in that figure is the gap between counting and deciding. At seven creases it is 40,320 against one.

The gap is governed by how common the answers are #

The essay reports that the distance between deciding and counting is total for maps and nothing for general patterns, and treats those as two facts. They are one fact, and the quantity that decides which way it falls is how plentiful the solutions are.

A decision procedure may stop at the first success, so its cost is the work of reaching one. If solutions are abundant it reaches one almost immediately and deciding is nearly free. If solutions are rare it has to look nearly everywhere before finding one, and deciding costs almost exactly what counting costs.

A counting procedure never stops early, so its cost is the whole space, whatever the density.

So the gap between the two is widest precisely where the decision is easiest, and that is not a coincidence — the decision is easy because the solutions are dense, and dense solutions are what leave counting with everything still to do.

Which explains both of the essay’s cases at once #

Run it on the two families and the reversal stops being a surprise.

A ruled map folds always, by a construction anybody can state in a sentence, and it folds in an enormous number of ways: a three-by-three map has one thousand three hundred and sixty-eight folded states. Solutions are as abundant as they can be, so deciding is trivial and counting is the hardest open problem in the subject. Maximum density, maximum gap.

A general crease pattern almost never folds — almost every drawn pattern fails at its first vertex — so a decision procedure searching for a folded state is looking for something that is very probably not there, and it has to exhaust the space to find out. Minimum density, no gap: deciding is already as expensive as counting, and that is exactly why the decision version is the one that is NP-hard.

The strip sits between them and shows the middle of the range. On an evenly creased strip every assignment folds, deciding is free and counting is not; on an uneven one few do, and the two costs converge.

So the essay’s warning that the four questions are not a hierarchy can be given a mechanism rather than only examples. They are not a hierarchy because their relative cost depends on the density of solutions, which is a property of the family and not of the questions — and a family can be chosen to put the gap anywhere between nothing and everything.

And listing, which is a different kind of expensive #

Listing looks like counting with the answers kept, and for the strip above it is. In general it is not, and the difference has a name.

A listing problem’s cost has two parts: the work of the search and the size of what comes out. For map folding at twelve stamps the output is 146,376 objects. No algorithm, however clever, writes 146,376 objects in less time than it takes to write 146,376 objects. The problem is not hard because the search is hard; it is hard because the answer is large.

That is a different phenomenon from NP-hardness and it deserves its own name, which it has: an output-sensitive cost, measured against the size of the answer rather than the size of the input. Judged that way, some listing problems that look catastrophic are efficient, and the distinction turns out to matter for most of folding’s counting questions.

Optimising, which nobody here can do #

The fourth question is the one this repository cannot answer at all, and saying so is more useful than gesturing at it.

Optimisation asks for the best folded state under some measure. The measures that matter in practice are physical: the fewest layers over any point, because layers are what a real material runs out of; the least total crease length, because creases are what a manufacturing process pays for; the most compact folded footprint, because that is what a deployable structure is for.

Every one of these is at least as hard as deciding, because an optimiser that returns anything at all has decided. And every one of them is harder in a second way: the optimiser has to know that nothing beats what it found, which means either exhausting the alternatives or having a bound.

The design side of the subject is entirely optimisation — packing circles to fit a base into a square is an optimisation problem, and it is one where the best known answers for most numbers of discs are conjectures rather than theorems. The honest position is that this site measures what a design achieves and does not claim any design is best.

The strip, where all four can be asked at once #

One dimension is the only place on this site where all four questions have answers, and it is worth watching them behave, because the behaviour is not what the general theory would lead anybody to expect.

Deciding a strip is easy in the sense that matters — it is not NP-hard, because the overlaps on a line form a chain rather than a tangle and chains cannot contain the cycles that make the two-dimensional question intractable. Counting a strip’s stackings is affordable at the sizes drawn here. Listing them is the same search with the results kept. And optimising over them is possible in principle, by listing and then comparing, which is a legitimate algorithm and a terrible one.

That last point is worth dwelling on. Optimisation is always solvable by listing, so the interesting question is never whether it can be done but whether it can be done without listing. For a strip of seven creases, listing costs forty thousand tests to compare one legal stacking against nothing. For a sheet, listing is not available at any price, so an optimiser has to find structure or find a bound — and the structure is what nobody has.

The evenly spaced row of the figure is the case that makes all four cheap at once: every assignment folds, so the count is 2ⁿ without any search, the listing is the whole set, and any optimisation over it is a choice among equals. A problem instance can be easy for reasons that have nothing to do with the problem.

What “hard” is being said about #

Two clarifications, because both get elided constantly and the second one is the more misleading.

NP-hardness is about a family, not an instance. No particular crease pattern is NP-hard; the problem is, and a problem is a set of instances. That distinction has consequences for how the result should be read, and they are the subject of the next rung.

The four questions are not a hierarchy of one problem. Prose in this area frequently says something like “counting is the harder version of deciding”. It is not a version. It is a different function with a different codomain, and the only general relationship is the one already noted — a count of zero answers a decision, so counting is at least as hard, and that is all that holds in general. For maps the gap is total; for general patterns it is nothing, because the bottom rung is already hard.

Where this site sits #

It is worth being explicit about which of the four questions each of this site’s solvers answers, because the answer is not uniform and reading a figure as though it were is easy.

The vertex checker decides nothing. It applies four local conditions at each vertex, all of them necessary, none of them sufficient, and what it cannot see is a whole essay of its own. Its job is to refuse patterns that are definitely wrong so a reader never folds one.

The layer solver decides and counts and lists, in one dimension only, by exhausting the orderings of the segments. That is why the strips on this site are short.

The map enumerator counts, in two dimensions, for ruled rectangles, and stops where the machine does.

The sequence simulator decides a different question — whether a machine can reach a state — and, when it succeeds, lists the sequence.

Nothing here optimises. Nothing here decides two-dimensional flat-foldability, and nothing here could: that is the NP-hard one, and a figure asserting it would be exactly the confident illustration this site refuses to make.

The idealisation underneath all four #

Every question above is asked of a zero-thickness sheet with infinitely sharp creases and no memory. Change that and the questions change with it, sometimes beyond recognition.

For a real sheet, “does it fold flat” stops being a yes-or-no question and becomes one about how much force and how much damage. The counting question becomes strange rather than hard: two stackings that differ only in the order of layers that never touch are the same physical object to a folder and different objects to the enumerator. And the optimisation question becomes the only one anybody with a factory cares about.

That is not an argument against the idealisation. It is the reason the idealisation is stated: the geometric versions of these questions are hard already, before any of the material difficulties are added, and separating the two is what lets the material ones be measured.

A fifth question, which is the one manufacturers ask #

The four above are the ones the literature is organised around. There is a fifth that sits underneath the whole of the previous ladder and that none of the four covers: can it be made?

That is not the decision question. A folded state can exist and be unreachable by any given machine, which a strip of two creases demonstrates. It is not the counting question either, and it is not optimisation, though a manufacturer optimising over sequences is doing something that looks like all three at once.

The reachability question has its own four versions, which is where this gets genuinely tangled and also where it stops being an academic taxonomy. Can this machine make it is a decision. In how many ways is a count. Which sequence is a listing. Which sequence is shortest is an optimisation, and it is the one a production line is actually solving, because the number of stations on the line is the number of folds it can afford.

So the four questions of this essay are really four questions per predicate, and folding has at least two predicates. That is not a complication invented for the sake of it — the two predicates have different answers on the same paper, and confusing them is how a pattern that provably folds ends up on a line that provably cannot make it.

Who asked these, and when #

The counting question for maps is Ulam’s, from the 1960s, and W. F. Lunnon computed the first values in 1968 and 1971 — the numbers this site’s own enumerator checks its arithmetic against. The decision question for general crease patterns was settled by Marshall Bern and Barry Hayes in 1996. The distinction between deciding and counting as complexity classes is Leslie Valiant’s, from 1979, and it was not made with paper in mind.

What folding contributes to that general story is an unusually clean pair of examples. Most subjects have to work to find a problem that is easy to decide and hard to count; folding has one that anybody can state in a sentence and that has been open since before the class of counting problems was defined.

Where the ladder goes next #

The word “hard” has been used freely here and it needs pinning down, because it is a statement about the worst instance a family contains and every crease pattern on this site is decided by a search that finishes at once. Those two facts are compatible, and understanding how is the difference between using the result and repeating it.

And the listing question has a shape of its own worth following: when the answer is exponentially larger than the question, efficiency has to be redefined, and folding is a subject where that is the normal case rather than the exception.