Which layer goes on top

A crease pattern with a mountain-valley assignment is not a folded object. It is a set of instructions about which way each line turns, and turning is only half of what folding does. The other half is stacking, and nothing in the assignment records it.

That omission is not a gap in the notation. It is the subject.

Two things a folded state has to say #

Consider what a complete description of a flat-folded sheet must contain.

It must say where every piece of paper ends up. That part is fixed by the crease positions alone: fold along a line and everything on one side reflects, and doing that repeatedly gives a map from the flat sheet to the plane which has nothing to do with mountains or valleys. Two patterns with the same creases and different assignments produce the same footprint.

It must also say, wherever two pieces of paper land on the same spot, which one is nearer the reader. That is a separate piece of data — an ordering of the faces that overlap — and it is what the assignment constrains without determining.

Everything hard about flat-foldability is in the second part. The first is arithmetic.

The asymmetry is easy to miss because the two halves are so unequal in how much attention they get. A crease pattern is a drawing, and a drawing carries the first half completely: the lines are where the paper bends, the colours are which way. The second half has no marks on the page at all. It is carried, if it is carried anywhere, in the folding sequence — and a folding sequence is a different document, usually much longer, and frequently not published alongside the pattern.

So the standard artefact of the subject records exactly the half that is easy and omits exactly the half that is hard. That is not a criticism of the notation; there is no obvious way to draw a stacking. It is an observation about why crease patterns are harder to read than they look.

The assignment constrains the order without fixing it #

The relation between the two is worth stating precisely, because it is often blurred.

At a crease, two faces meet along an edge and the paper turns from one to the other. That turn is a U-shape in cross-section, and it opens either toward the reader or away — which is exactly what mountain and valley mean. So an assignment fixes, for each crease, whether the outgoing face is above or below the incoming one.

What it fixes is a comparison between adjacent faces. It says nothing about two faces that overlap but do not share a crease, and in a pattern of any size most overlapping pairs are of that kind. The assignment gives a set of local comparisons; the layer order is a total ordering consistent with all of them; and a set of comparisons can be consistent with many orderings, or with none.

There is a tempting shortcut that is wrong, and it is worth killing early: that a mountain means “the next face goes above” and a valley means “below”. A plain accordion refutes it. Its creases alternate mountain and valley all the way along, and its layers stack monotonically, one on the next, with no alternation at all. What alternates as well as the letters is the direction the paper is being travelled in, and the two alternations cancel.

So the rule is a product of two things rather than a property of one, and any account of layer ordering that reads the letters directly off the stack has lost the sheet’s orientation somewhere. The generator that draws the strips here carries the direction explicitly for exactly that reason.

The two forbidden patterns #

There are exactly two ways a proposed stacking can be wrong, and both are pictures of paper trying to pass through paper.

Taco-tortilla. A crease is a fold, and a fold has no gap in it. So a flat face that crosses the place where a fold sits may not lie between the two faces the fold joins — it would have to thread through the closed end of the U. It may lie above both or below both, and nowhere else.

Taco-taco. Two folds may sit at the same place, both opening the same way. Their layer pairs may then be nested, one inside the other, or entirely separate. They may not interleave, because interleaving asks each fold to pass through the other.

That is the complete list. Every self-intersection in a flat-folded sheet, however complicated it looks, decomposes into instances of one of those two — a result that is easy to believe once the pictures are in front of the reader and takes some care to prove.

The names come from Erik Demaine’s teaching of the subject and they are better than they sound. A fold seen edge-on is a taco: two faces joined round a closed end. A face passing through with no fold at that place is a tortilla: flat, open at both ends. So the two conditions are “a tortilla may not go into a taco” and “two tacos may not interleave”, and once stated that way they are difficult to forget.

What makes them worth having is that they are local in the folded picture while being global in the flat one. Two faces that end up in the same place may come from opposite corners of the sheet, so the condition connects parts of the pattern that share no crease and no vertex. That is precisely the property that makes the problem hard, and it is also what makes the conditions checkable: given a proposed stacking, verifying it is a matter of running down a list of overlaps.

Why the vertex conditions cannot see them #

The two rules are trivial to state. The interesting question is why Kawasaki and Maekawa miss them entirely, and the answer is about what those conditions are looking at.

Kawasaki is a statement about the angles at one point. It asks whether the sectors alternate into two groups summing to a straight angle each, and it involves no other point of the sheet.

Maekawa is a statement about the letters at one point. It counts mountains and valleys among the creases meeting there.

Neither has any way of referring to a face that is not incident on that vertex. The forbidden patterns above all involve at least three faces, and in the taco-tortilla case the offending face need not touch the crease it pierces at all — it merely covers the same ground once the sheet is folded. There is no local test at a vertex that could notice it, because the information is not local.

Big-little-big is the interesting intermediate case. It is still a condition at a single vertex, but it is derived from a stacking argument: a strictly smallest sector flanked by two creases of the same assignment forces the two panels beside it to occupy the same place. So the layer question does reach back into the local theory — but only as far as one vertex can see, which is one sector.

That is the whole extent of the reach, and it is worth appreciating how short it is. Big-little-big is the strongest condition anybody has found that can be checked at one point, and it catches only the case where the two colliding panels are the immediate neighbours of the smallest sector. Move the collision one panel further out and no vertex condition sees it.

Which is the honest summary of the local theory: it is complete for one vertex, it is a filter for two, and it is almost nothing for many. The three conditions between them decide the single-vertex case entirely — and there is no fourth condition waiting to be found that would decide the next case, because if there were, the hardness result would be false.

Which theorem was checked, and how #

The stacking in the figures above is not drawn. It is found.

The one-dimensional machinery in this repository takes a strip with creases and an assignment, computes where each segment lands, derives the comparison each crease imposes between its two segments, and then searches the orderings for one satisfying every comparison together with both non-crossing rules. Where a stacking exists it is returned; where none does, the figure says so rather than drawing something plausible.

The search is exhaustive over permutations, which is a factorial algorithm and entirely adequate for the six or seven segments a figure can show. It is not the algorithm the literature gives, and the essays do not pretend otherwise: a linear-time method exists for the one-dimensional case and is a different object.

The check on the checker is worth stating, because a search that accepted everything would look identical from outside. Summed over every assignment, the number of stackings the search finds for a strip of n equal segments reproduces the known counts of the ways of folding a strip of n stamps — 1, 2, 6, 16, 50, 144, 462 — for n up to seven. Those numbers were computed by other people by other means, and matching all seven is not something a broken search would do.

Two vertices are already the general case #

The jump from tractable to intractable is usually imagined as a gradient, with small patterns easy and large ones hard. It is not a gradient. It happens between one vertex and two.

One vertex: three conditions, all arithmetic, a linear-time algorithm and a proof that they are sufficient. Nothing is left over.

Two vertices sharing a crease: each imposes an ordering on the region they have in common, and those orderings have to agree. Nothing in either vertex’s conditions says anything about the agreement, because the agreement is a statement about a pair. So the very first case with more than one vertex is already outside the local theory.

Many vertices: the agreements form a constraint graph, the graph can contain cycles, and cycles can be unsatisfiable. That is the hardness, and it is not a new phenomenon appearing at scale — it is the two-vertex phenomenon, repeated until it becomes expensive.

That explains something otherwise puzzling about the literature, which is the absence of an intermediate theory. There is a theory of one vertex and a complexity result about many, and nothing in between. There is nothing in between because there is no regime in between for a theory to describe.

Where the difficulty enters #

The rules are simple, the objects are finite, and the problem is still intractable. It is worth being precise about where that happens.

Consider two overlapping faces. Their relative order is one binary choice. Consider a chain of overlaps in which each consecutive pair’s order is forced by the local geometry: the choices propagate, and a cycle of forced comparisons can be contradictory in the way “A above B, B above C, C above A” is.

A set of binary variables with constraints that can form cycles is exactly the shape of a satisfiability problem, and Marshall Bern and Barry Hayes showed in 1996 that the correspondence is close enough to run in both directions. They build crease patterns whose layer-ordering constraints implement a boolean formula, so the pattern folds precisely when the formula is satisfiable, and the general problem is therefore NP-hard.

The sharper form of their result is the one that matters here: it is NP-hard even when a valid mountain-valley assignment is given. The difficulty is not in choosing the folds. It is in stacking them.

The idealisation this rests on #

Layer ordering is a discrete question only because the paper has no thickness.

Give the sheet a thickness and the ordering stops being a permutation and becomes a set of positions, faces that were coincident become merely close, and the crisp forbidden patterns turn into inequalities with tolerances in them. That is not a small perturbation of the problem; it is a different problem, and it is the one everybody who builds anything has to solve.

The zero-thickness model earns its place by being decidable in principle and by being what the theorems are about. It should not be mistaken for a description of paper. A real sheet resolves an impossible ordering by bulging slightly, and a model with no thickness has no bulge available, so it reports impossibility where paper reports a slightly untidy result.

The surprise: the order is data, and it can be counted #

There is a habit of thinking of the layer order as something that follows from the pattern, an implementation detail to be worked out once the real design is done. Counting says otherwise.

For a fixed set of creases and a fixed assignment, the number of valid stackings is usually greater than one. The five-segment strip in the second figure has several; a strip with unequal segments can have eleven for one assignment and exactly one for another. Those are genuinely different folded objects made from the same instructions, distinguishable by looking at the edge of the stack.

So a crease pattern with an assignment does not specify a model. It specifies a family, and how large the family is depends on the pattern in a way nobody has characterised. That is the honest reason a published crease pattern is hard to follow: the information a folder is missing is not written down anywhere, because there is no established notation for it.

The counting also gives a way to say what a hard pattern is that does not appeal to the reader’s experience. A pattern with many valid stackings is forgiving, because a folder who guesses will probably guess one of them. A pattern with exactly one is unforgiving, because every choice but one is a dead end that may not announce itself for several more steps. The number of stackings is a measure of how much slack the design has, and it is computable for small cases and unknown for real ones.

None of this is visible on the page. Two patterns can look equally simple and differ by an order of magnitude in how many ways they can be assembled.

What is done in practice #

Given that the general problem is hard, it is worth saying what people actually do, because the field is not paralysed.

Layer ordering is set up as a constraint problem — one variable per overlapping pair, one clause per instance of a forbidden pattern — and handed to a general solver. For patterns of the size anybody designs, this returns an answer quickly, because designed patterns are symmetric and modular and their constraint graphs are correspondingly tame.

There is a family of patterns where the ordering comes for free, and it is where all the engineering happens. A Miura fold is periodic, so its layer constraints repeat and the repetition makes them consistent by symmetry. A twist tessellation is the same story with a larger unit. Structure is what makes the hard case rare, and every manufactured fold is structured.

The other route is to avoid the question. A folding sequence determines the layer order constructively: each fold is made on top of what is already there, so the stacking is built rather than discovered. A crease pattern published in a book is a record of a sequence somebody carried out, and its foldability is established by demonstration rather than by search. The hard direction — pattern to sequence — is the one that is intractable, and it is the direction computational design has to go in.

The ladder from here #

Later rungs against this anchor: the Bern and Hayes reduction, drawn as the gadgets it is built from. Layer ordering as a constraint satisfaction problem, and what a modern solver does with a real pattern. The proof that taco-taco and taco-tortilla are the complete list. The one-dimensional case, where the ordering is decidable and the reason is structural. Counting folded states of a given pattern, which is a hard enumeration problem in its own right. And the notation question — what a crease pattern would have to carry to specify a folded state uniquely, and why nobody has settled on one.

The assignment is the part everybody draws, because it is the part that fits on the paper. The part that does not fit on the paper is the part that is difficult.