The gadgets that make it hard

That deciding whether a crease pattern folds flat is NP-hard is usually stated and then left alone, as though it were a wall. It is not a wall. It is a machine, and the machine is made of paper.

The reduction Marshall Bern and Barry Hayes published in 1996 takes an instance of a satisfiability problem and builds a crease pattern that folds flat if and only if the instance is satisfiable. Everything about how hard the folding problem is follows from that one construction, and the construction is worth seeing, because it says something the bare statement of hardness does not: where the difficulty is.

The difficulty is not in the angles #

A crease pattern presents three questions, and it is easy to assume the hardness is spread across them.

The first is whether the angles permit folding at all — developability and Kawasaki, both settled at each vertex by arithmetic on the sector angles, both checkable in time proportional to the number of creases.

The second is which creases are mountains and which are valleys. There are exponentially many assignments, and the local conditions discard most of them while leaving exponentially many behind. This looks like the hard part and is not.

The third is which layer goes above which. Once the angles and the assignment are fixed, the folded sheet is a stack of flaps, and the question is whether the flaps can be ordered so that no two of them pass through each other. That question is the one with no local answer.

Bern and Hayes settled the matter by proving hardness even when the assignment is given. Hand the algorithm a pattern with every crease already labelled and the problem stays NP-hard. Whatever the difficulty is, it is not the search over assignments — it is what remains after that search has been done for free.

A wire #

The first gadget is the one the figure at the top shows, and it is almost disappointingly simple.

Take a strip of paper with four creases, evenly spaced, assigned valley, mountain, mountain, valley. Fold it. The shape of the result is completely determined — the creases are where they are and the letters say which way each turns — and yet the folded object is not determined, because two of the flaps can be stacked in either order. Enumerating every stacking that satisfies the non-crossing conditions gives exactly two.

Two states, no more and no less, in a piece of paper whose geometry is fixed. That is a bit.

The value is carried in the layer order rather than in the shape, and this is the point on which the whole construction turns. A gadget whose value showed in its shape would be a gadget whose value a local test could read. A gadget whose value is in the stacking is invisible to every condition at every vertex, which is why the conditions cannot decide the problem.

Chain such strips together and the bit travels: the stacking at one end constrains the stacking at the next, so a value set in one place is readable somewhere else. That is a wire, and a wire is the first thing any reduction needs.

A clause #

The second gadget is a junction, and it is where this essay stops being able to verify what it describes.

Three wires meet in a region of the sheet. The geometry is arranged so that the three layer orderings cannot all agree: any stacking in which all three carry the same value has two flaps passing through one another, and every other combination is fine. That constraint — not all three equal — is a clause of the not-all-equal satisfiability problem, which is NP-complete.

A formula is then a sheet. Each variable is a wire, each clause is a junction, the wires run between them, and the whole thing is one crease pattern with one mountain-and-valley assignment. It folds flat exactly when there is a way of setting every variable that satisfies every clause.

Nothing in the machinery of this site can check that junction. The layer solver here is one-dimensional: it decides stackings for a strip, which is why the wire is verifiable and the junction is not. Deciding the junction means deciding layer order in two dimensions, and that is the problem the reduction is about. Drawing it and asserting it would be exactly the kind of confident illustration this site refuses to make.

Reading a formula off a sheet #

It is worth being concrete about what “the pattern encodes the formula” means, because the phrase does a great deal of work and hides a design problem.

A formula has variables and clauses, and a clause refers to variables that may be anywhere in it. A sheet of paper is two-dimensional and its gadgets are laid out on a plane, so the wires connecting variables to the clauses that mention them have to be routed, and routes cannot cross — or rather, where they must cross, a crossing gadget is needed that lets two bits pass through one another without either changing.

Every reduction that builds a planar object out of a non-planar problem meets this, and the standard answer is the standard one here: a crossover gadget, plus the observation that not-all-equal satisfiability stays NP-complete when the formula’s variable-clause graph is planar, so most of the routing problem can be assumed away. The construction is then a layout: variables in a row, clauses above them, wires between, crossings resolved.

What this means for the reader is that the size of the sheet is not the size of the formula. It is the size of the formula’s layout, which is larger by a polynomial factor. That is fine for a hardness proof — polynomial factors are what a reduction is allowed to spend — and it is one more reason these patterns are not objects anybody would fold.

What a reduction actually proves #

It is easy to overread this result, and the overreading is common enough to be worth heading off.

The reduction says that no algorithm decides flat-foldability for every crease pattern in polynomial time, unless P equals NP. It says nothing about any particular pattern. The patterns the reduction builds are strange objects with a great many long thin flaps, engineered so that their layer orderings encode a formula; they are not what a crease pattern from the folding tradition looks like, and nobody would ever draw one on purpose.

For an ordinary pattern the question is usually easy. A Miura is decided by symmetry; a box-pleated base is decided by construction, because it was built by a procedure that produced a folding along with the pattern; a strip is decided in linear time. Hardness is a statement about the worst case, and origami’s worst cases are constructed rather than encountered.

What the result does establish, and this is the useful half, is that no local test will ever be enough. If some collection of conditions at vertices decided flat-foldability, it would decide the reduction’s patterns too, and it would therefore solve satisfiability in polynomial time. So the gap between the local conditions and the global answer is not a gap in anybody’s cleverness. It is permanent, unless something very surprising is true about computation in general.

The easy side of the boundary #

A hardness result is only half a piece of information. The other half is where the problem stops being hard, and for flat-foldability the boundary is unusually well mapped.

In one dimension everything is easy. A strip of creases folds flat if and only if a short local rule holds along it, the valid stackings can be listed, and the whole question is decidable in linear time. The reason is worth stating precisely, because it is the reason the second dimension is different: on a strip, the flaps that can interfere with a given flap are the ones that wrap the same end, and there are two ends. On a sheet there is no such bound.

Restricting the folds rather than the sheet also works. If the pattern must be folded by a sequence of simple folds — each one folding everything at a single line, as a machine or a sheet-metal press would — the problem becomes tractable again, because the sequence of operations orders the layers as it goes and there is no search. The price is that most crease patterns are not simple-foldable, including nearly every interesting one.

And restricting the pattern works. A pattern built by a construction, rather than drawn and then asked about, arrives with a folding already attached: the fold-and-cut construction produces a pattern from a straight skeleton and the skeleton is the certificate. So does every base built by packing circles. Design almost never poses the decision problem, because a designer is not handed a pattern — a designer builds one, and the building is a proof.

Which theorem was checked, and how #

The wire is checked. The strip solver enumerates every stacking of a one-dimensional strip that satisfies the non-crossing conditions, and the generator refuses to draw a wire that does not have exactly two — so an edit to the assignment, the spacing or the solver that changed the count would stop the build rather than produce a figure with a wrong caption under it.

That solver is itself checked against something computed elsewhere. Summed over every assignment, the stackings it finds must reproduce the published counts of the ways of folding a strip of $n$ stamps — 1, 2, 6, 16, 50, 144, 462 — and it does, for all seven terms. A solver missing a rule overcounts and one with a rule too strong undercounts; agreeing on seven terms is not something a broken implementation manages by accident.

The junction is not checked, and the figure says so on its face rather than in a footnote.

What the picture cannot show #

The wire’s two states are drawn as two layer diagrams, and a layer diagram is a schematic: the flaps are drawn separated so they can be told apart, and in the folded sheet they are in contact. Nothing about the vertical spacing in those pictures is a measurement.

More importantly, the figure cannot show the thing the reduction is about, which is a formula. A wire is one bit; a satisfiability instance worth the name has thousands, and the crease pattern that encodes one would be a sheet with tens of thousands of creases whose picture would be a grey rectangle. The reduction is a proof technique rather than a drawing, and this essay’s figures are of its parts.

The idealisation underneath #

The whole argument assumes paper of zero thickness. That is the first of the four things that are not true, and here it is doing more work than usual.

The gadgets rely on flaps sliding past one another to reach a different stacking, and on the stack being infinitely compressible so that any number of layers occupies no height. A real sheet with real thickness cannot form most of these configurations at all — which does not rescue the problem, because it makes it worse: the physical question adds constraints and does not remove any. It is a reminder that “flat-foldable” is a statement about a mathematical object, and the sheet on the table is a different object.

The surprising connection #

The reduction has a corollary that reads oddly the first time.

Since the pattern folds flat exactly when the formula is satisfiable, and since counting satisfying assignments is harder still, counting the foldings of a crease pattern is at least as hard as counting satisfying assignments — a problem in a complexity class above NP. So the question “how many ways does this fold” is not merely difficult in practice. It is difficult in a way that has been classified.

That connects this rung to a question that has nothing to do with satisfiability and was asked long before anybody thought about complexity: in how many ways does a map fold. The answer is unknown past a handful of small cases, and it is unknown in the specific sense that the numbers have to be computed one at a time by exhaustive search.

There is a second connection, and it runs the other way. Because the reduction encodes arbitrary formulas, a crease pattern can be built to compute — the folded state of a suitable sheet answers a question that was posed as a formula. Nothing practical follows from that, since folding the sheet is at least as hard as answering the question, but it does settle what kind of object a crease pattern is. It is not a picture of a shape. It is a specification, with the expressive power of a logical formula, and the folded state is its solution.

What the counting result does not say about maps #

There is a step in the paragraph above that this essay’s own argument forbids, and it is worth catching because it is the exact overreading the section on what a reduction proves warns against.

Counting the foldings of a general crease pattern is hard because the reduction builds patterns that encode formulas. A map is not one of those patterns. It is a rectangle ruled into squares — the most restricted family in the subject, with every crease at a right angle, every panel congruent, and no long thin flaps anywhere.

A hardness result about a family says nothing about a subfamily. One-dimensional strips are a subfamily and they are decidable in linear time; simple-foldable patterns are a subfamily and they are tractable; patterns built by a construction arrive with a certificate. Maps could perfectly well be another such case, and the reduction offers no evidence either way.

So the honest statement about map folding is the one the essay makes and then undercuts: nobody has found a formula, and nobody has shown the problem is hard. It sits in the small and uncomfortable set of questions that are open in both directions, which is a more interesting position than provably difficult and is the position the record actually supports.

Which makes the map case the sharper open question #

That reframing improves the connection rather than removing it, because it says what the two results have in common and what they do not.

They share the shape of the difficulty: both are about layer orderings rather than about angles or letters, and in both cases the local structure decides nothing. That is a real kinship and it is why the two belong on the same page.

What they do not share is a status. Flat-foldability in general is classified. Map folding is unclassified, and a formula for the stamp numbers is not ruled out by anything anybody has proved — which is exactly why sixty years of attention has produced twelve integers and no theorem, rather than a theorem explaining why there are only twelve integers.

An open problem that might yet fall is a better advertisement for a subject than a closed one that cannot, and this essay’s own rule about worst cases is what makes the distinction available.

Who found it, and when #

Marshall Bern and Barry Hayes gave the reduction in The Complexity of Flat Origami, at the Symposium on Discrete Algorithms in 1996. The result is usually quoted as “flat-foldability is NP-hard”, and the paper’s sharper statement is the one worth quoting: it is NP-hard even when the mountain-and-valley assignment is given, which is what locates the difficulty in the layers.

The problem was refined afterwards. Akitaya, Cheung, Demaine and others tightened the class of patterns for which hardness holds, and the one-dimensional and simple-fold restrictions were shown to be tractable, which is the standard way a hardness result is followed up: find the boundary, and then live on the easy side of it.

The ladder from here #

This is the deepest rung on flat-foldability that this site currently carries, and it is deep in the sense of assuming the most: it takes the local conditions, the layer question and the gap between them as known.

Where the ladder goes next is sideways rather than up. Map folding asks the counting question on the most regular pattern there is and finds it open; the fold-and-cut theorem shows a whole family of patterns whose foldings are constructed rather than searched for. Both are cases where the general difficulty proved here is real and where something is known anyway, which is the ordinary condition of a subject with a hardness result in it.