A strip is decidable

Deciding whether a crease pattern folds flat is NP-hard. Deciding whether a strip folds flat takes linear time. The gap between those two sentences is one dimension, and understanding what that dimension buys is more instructive than either result on its own.

What a one-dimensional pattern is #

A strip of paper with creases across it, and a letter at each crease. That is the whole object — and it is a cross-section of the two-dimensional problem rather than a different subject.

Folding it is the same operation as folding a sheet, restricted: each crease reverses the direction of travel, so the folded image of the strip is a walk along a line that doubles back at every crease. The image is determined by the crease positions and nothing else — the assignment does not move any paper, exactly as in two dimensions.

What the assignment does is fix, for each crease, whether the outgoing segment sits above or below the incoming one. And the layer order has to be consistent with all of those comparisons while breaking neither of the two non-crossing rules.

So the problem has the same three ingredients as the two-dimensional one. What it lacks is the thing that makes them interact badly.

Why the chain matters #

Here is the structural reason, and it is short enough to state before the evidence.

In two dimensions, the set of faces that overlap a given face is not ordered by anything. Face A can overlap B and C without B and C overlapping each other, so the constraints form a graph, and a graph can contain a cycle: A above B, B above C, C above A. A cyclic set of order constraints is unsatisfiable, and detecting whether a large system contains one is the hard part.

In one dimension, every segment that overlaps another does so along an interval of the same line. The intervals are ordered by position, and the constraints inherit that order. The constraint structure is a chain rather than a general graph, and chains do not admit cycles.

That is the whole difference. Not size, not the number of creases, not the amount of symmetry: the shape of the constraint structure. Add a second dimension and overlaps stop being linearly ordered, cycles become possible, and the problem becomes as hard as satisfiability.

Every assignment of an evenly creased strip folds #

The most surprising result in the one-dimensional case is easy to state and easy to disbelieve.

Take a strip divided into equal segments by evenly spaced creases. Then every mountain-valley assignment folds flat. All of them, with no exceptions, for any number of creases.

That is not what the two-dimensional intuition predicts. In two dimensions, valid assignments are a shrinking minority: a degree-four vertex admits four of sixteen, and the preliminary base a hundred and twelve of two hundred and fifty-six, and the fraction falls as the pattern grows. Here the fraction is one.

The reason is that equal segments make every fold coincide with every other. Every crease lands at one of two folded positions, every segment covers the whole folded interval, and the layers can always be nested rather than interleaved because there is never a partial overlap to force an interleaving. Nesting is always available, so a stacking always exists.

Break the evenness and the picture changes at once. A strip with one short segment between two creases admits only half its assignments, and the ones it rejects are exactly those that put the same letter on both sides of the short segment.

Half for each short segment, and a floor that follows #

The halving generalises, and the general form gives the one-dimensional case a guarantee the two-dimensional case has nothing like.

A segment strictly shorter than both its neighbours forbids the two creases bounding it from carrying the same letter — two of the four ways to letter that pair — so it halves the count. Two such segments can never be adjacent, since neither could then be shorter than the other, so they share no crease and their halvings are independent. For a strip of $n$ creases with $L$ strictly-short segments the first-round count is

$$2^{\,n-L},$$

which is $2^n$ when the spacing is even and $L = 0$, and $2^{n-1}$ for the essay’s one-short-segment strip. It is an upper bound rather than a verdict, because crimping a short segment away merges its neighbours into one that may itself be short — the recursion is what turns the count into an answer.

Which puts a floor under the one-dimensional case #

The short segments being non-adjacent bounds how many there can be: at most about half the interior segments, so $L \leq (n-1)/2$ and

$$\text{admissible} \;\geq\; 2^{(n+1)/2} \;>\; \sqrt{2^{\,n}}.$$

At least the square root of all assignments of any strip whatever fold flat, however awkwardly its creases are spaced.

Two dimensions has no such floor. There the admissible fraction falls with the number of vertices, which grows with the sheet’s area rather than its width, so a large pattern’s surviving fraction goes to zero far faster than any strip’s can. That is the same one-dimension difference the chain argument names, arriving as a count rather than as a structure.

The accordion and the spiral #

Two extreme assignments are worth looking at directly, because they bracket everything else.

The accordion alternates: mountain, valley, mountain, valley. Its layers stack monotonically — the first segment at the bottom, the last at the top, in order — and there is exactly one valid stacking however many creases it has. It is the pattern with the least freedom and the most reliability, which is why every deployable structure that only needs to fold in one direction uses it.

The spiral gives every crease the same letter. The strip wraps round and round itself, each turn outside the last, and with equal segments this folds perfectly well. With unequal segments it usually does not, because the wrapping requires each successive turn to have room and a short segment in the wrong place removes it.

Between the two extremes the number of valid stackings varies by more than an order of magnitude for the same crease positions. One assignment of a four-crease strip admits eleven stackings; another admits exactly one. Nothing in the pattern’s appearance predicts which.

That variation is the one-dimensional shadow of a fact about the general problem. A crease pattern with an assignment does not describe a folded object; it describes a set of them, and the size of that set is not something the pattern wears on its face.

Big-little-big, in one dimension #

That last observation deserves its own name, because it is a theorem from the two-dimensional theory turning up unannounced.

The big-little-big lemma says that a sector strictly smaller than both of its neighbours must be flanked by creases of opposite assignment, or the panels either side of it collide. It is stated about the angles at a vertex, and it looks like a statement about angles.

Take a strip with segments of lengths 0.25, 0.10 and 0.65. The middle segment is strictly shorter than both neighbours. Of the four assignments of its two creases, exactly two fold — and they are precisely the two that give the two creases different letters.

Nobody put that rule into the one-dimensional machinery. The search knows about the two non-crossing conditions and about the comparisons the assignment imposes, and nothing else; the big-little-big pattern falls out of running it. Which is the useful way to meet a theorem: as something a general procedure keeps producing, rather than as a rule to be remembered.

The generalisation is clear once seen. Big-little-big is not about angles. It is about a piece of paper that is short compared with its neighbours, and the fact that the two folds at its ends have nowhere to go if they both wrap the same way. Angles are how “short” is measured at a vertex; lengths are how it is measured on a strip.

Which theorem was checked, and how #

The searches behind these figures decide rather than estimate, and there is an external check that they decide correctly.

The procedure computes the folded position of every segment, derives from the assignment which of each adjacent pair sits higher, and then enumerates the orderings of the segments, rejecting any that violates an adjacency comparison, puts a segment through a fold, or interleaves two folds. Where an ordering survives it is returned; where none does, the strip does not fold, and that is a proof rather than a failure to find one, because the enumeration was exhaustive.

The check is a count that other people computed by other means. The number of distinct ways to fold a strip of n labelled stamps is a known sequence — 1, 2, 6, 16, 50, 144, 462 for n up to seven. Summing the number of valid stackings over every assignment of an evenly creased strip should reproduce it exactly, because every folding corresponds to exactly one assignment together with one stacking. It does, for every value up to seven.

That is worth more than it might appear. A search with a rule missing would overcount; a search with a rule too strong would undercount; and matching seven terms of an independently computed sequence is not something a broken implementation does by chance.

Map folding, which is the same question and is open #

The obvious next question is what happens with a rectangular grid, and the answer is that nobody knows.

A map is a rectangle creased into a grid, and map folding asks whether a given mountain-valley assignment of the grid lines can be folded flat. It is the most natural two-dimensional generalisation of the strip and it has been studied since the 1960s.

For an n × 1 grid — a strip — the answer is the tractable one above. For an n × m grid the general question was open for decades and the general case is now known to be hard. What is not known is a clean characterisation for small grids, or a formula for the number of ways of folding an n × m map; the counts are computed by exhaustive enumeration and the sequence has been extended only a little way.

So the boundary between the two regimes runs right through the simplest family anybody could have chosen. One row is easy. Two rows are already the general problem.

Where the model stops #

Exhaustive, not linear. The search here is factorial in the number of segments, which is fine at six and hopeless at twenty. The literature’s algorithm is linear time and works by a greedy sweep; this is a different object and the figures do not claim otherwise.

Zero thickness. Every layer is a plane with no depth, so a stack of forty is as thin as a stack of two. A real strip of forty layers has a measurable thickness and the outer layers no longer reach, which is the problem that starts everything in engineering.

No creases in the other direction. A strip is one-dimensional because its creases are all parallel and go all the way across. A single crease that stops halfway makes the pattern two-dimensional, and the tractability goes with it.

The strip is not a design. Nothing here is about making anything. The one-dimensional case is a laboratory for the general problem, and its practical descendants — the accordion, the pleat — are the least interesting patterns in the subject rather than the most.

Simple folds are a different question. Deciding whether a strip folds flat and deciding whether it can be folded by a sequence of simple folds — each one folding everything along a single line — are separate problems with separate answers. The second is also tractable in one dimension and also becomes hard in two.

Nothing is said about how to fold it. A stacking is a description of the end state. Getting a physical strip into that state may require moving layers through one another on the way, and the model has nothing to say about the motion.

The strip has no width. A one-dimensional pattern is a cross-section, and treating it as a strip of paper assumes every crease runs the full width. That assumption is what keeps the problem one-dimensional and it is exactly what a real strip of paper violates the moment a crease stops short.

What the counts are actually counting #

The stamp-folding numbers deserve a second look, because what they count is easy to state and easy to get wrong.

A folding of a strip of n stamps is a way of stacking the n segments so that consecutive ones remain joined and no two joins cross. It is not a mountain-valley assignment; several foldings can share an assignment, and every folding determines one. So the sequence 1, 2, 6, 16, 50, 144, 462 counts folded objects, and the number of assignments is the much smaller 2 raised to n − 1.

For seven stamps that is 462 foldings against 64 assignments, so an assignment admits seven stackings on average. The average conceals a wide spread: some assignments admit one and some admit dozens, and the distribution is the interesting object rather than the total.

The sequence grows roughly exponentially and its exact growth rate is not known. That is a fair summary of the whole area: the smallest, cleanest, most completely tractable case in the subject has a counting problem attached to it that nobody has solved. Decidability and enumeration are different questions, and being easy to decide buys nothing at all toward being easy to count.

The surprise: this is where the tractable island ends #

There is a natural expectation that hard problems have a family of easy special cases shading gradually into the hard ones, and that the one-dimensional result is the first of several.

It is not. The tractable cases in flat-foldability are a short list and they do not shade into anything: the single vertex, the one-dimensional strip, and a handful of structured families like the Miura fold where the answer is known by construction. Between those and the general problem there is nothing.

The reason is the same reason as before. Each tractable case is tractable because its constraint structure cannot contain a cycle — a single vertex has too few faces, a strip has a linear order, a Miura is periodic and its cycles are all consistent by symmetry. There is no partial relaxation of “no cycles”; either the structure admits them or it does not, and admitting them is sufficient for hardness.

So the map of the subject is not a gradient with easy at one end. It is a small set of islands, each easy for a structural reason, in an ocean that is uniformly hard. The fold-and-cut theorem looks like a counterexample and is not: it constructs a pattern rather than deciding one, and construction is a different problem.

The same reading explains why the vertex conditions stop where they do. They are complete for one vertex because one vertex has no cycles to contain, and they are only a filter for two because two vertices already can.

Who found it, and when #

The one-dimensional problem is older than the two-dimensional one, and it arrived as a puzzle rather than as a theorem.

The contrast with the two-dimensional counting is instructive: there the local conditions only filter, so the numbers are candidate sets rather than answers, and here they are answers.

Stamp folding — in how many ways can a strip of n stamps be folded into a pile — was posed in the nineteenth century and computed by hand for small n long before anybody had a computer. The counts appear in the recreational literature well before they appear in a paper.

The algorithmic statement is much more recent. Marshall Bern and Barry Hayes’s 1996 paper, which established the hardness of the general problem, also observed the one-dimensional case as the contrasting tractable one. Erik Demaine, Martin Demaine, Anna Lubiw and others developed the one-dimensional theory properly through the late 1990s and 2000s, including the linear-time algorithm and the analysis of simple folds.

The historical order is the useful one to notice. The counting question came first and stayed a curiosity for a century; the complexity question came last and is what made the counting question look like part of a subject.

The ladder from here #

Later rungs against this anchor: the linear-time algorithm for one-dimensional folding, which is a greedy sweep and worth seeing. Simple foldability, where the question is about sequences rather than end states. Map folding and the enumeration of n × m grids. The stamp-folding sequence and what is known about its growth. The relationship between one-dimensional folding and meander enumeration, which is the same combinatorics dressed differently. And the question of which two-dimensional families inherit the chain structure, since that is what would extend the island rather than merely mapping it.

The dimension is not a detail. It is the whole difference between a problem with an algorithm and a problem with a hardness proof.