Origami & Folding
what one sheet can do
Flat-folding

Local is not global

Every vertex can satisfy every condition and the sheet still not fold. Deciding whether a whole crease pattern folds flat is NP-hard, which means no figure will settle it and no algorithm will scale.
16 min read 7 figures Local rules, global behaviourFlat is rare

The single-vertex problem is completely solved. Three conditions, all arithmetic, and a linear-time algorithm that produces a folded state when one exists.

That is where the good news ends.

Every vertex passes, which is not enoughThe local conditions are checked at each vertex independently, and a pattern can satisfy all of them and still fail to fold, because the layers have to stack without passing through one another. Deciding that for a general pattern is NP-hard, so no figure can settle it.6 interior vertices, every one satisfying both theoremswhat the local tests seeangles at each vertexassignment at each vertexwhat they cannot seewhether layer 3 passes through layer 7whether a flap has room to existwhether the order is consistent everywhereBern and Hayes, 1996: NP-hardso this pattern is checked, not proved
Fig. 1 A pattern where every interior vertex satisfies every local condition. That is necessary for the sheet to fold and is not sufficient, and the gap between the two is the central difficulty of the subject.

Checking every vertex of a crease pattern establishes only that the pattern is not obviously impossible. It does not establish that it folds.

What the vertex conditions miss

Each condition is evaluated at one point using only the creases meeting there. That is what makes them cheap and it is what they cannot see.

Layer ordering. A folded sheet has layers, and at every point they are in some order. Each vertex imposes constraints on the local ordering, and where two vertices share a region their constraints must agree. Nothing in Kawasaki or Maekawa examines that.

Self-intersection. Paper cannot pass through paper. A pattern can satisfy every vertex condition and require, in the folded state, that two panels occupy the same place. The vertex conditions have no view of any panel other than the four or six at their own point.

Global consistency. The orderings at many vertices form a system of constraints. Systems of constraints can be unsatisfiable even when every individual constraint is fine, and that is exactly what happens here.

So the local conditions are a filter. Anything failing them certainly does not fold; anything passing them might.

A vertex that folds flatFour creases at one point, with the sectors between them measured and both flat-folding conditions evaluated. Kawasaki constrains the angles and Maekawa constrains the assignment; a vertex needs both, and they are independent of one another.VMMM60°90°120°90°Kawasaki60° + 120° = 180°90° + 90° = 180°both 180° — satisfiedMaekawa3 mountains, 1 valleysdifference 2exactly 2 — satisfiedangles sum to 360°which is what a flat sheet requiresmountainvalley
Fig. 2 What a local check sees: one point, its angles and its assignment. Everything about how this vertex relates to any other is outside the picture.

The hardness result

Marshall Bern and Barry Hayes proved in 1996 that deciding whether a general crease pattern folds flat is NP-hard.

The proof is a reduction: they encode a known NP-hard problem — a variant of satisfiability — into a crease pattern, arranged so that the pattern folds flat exactly when the logical formula is satisfiable. Any efficient algorithm for flat-foldability would give one for satisfiability.

They proved something slightly stronger and more interesting: even when a valid assignment of mountains and valleys is given, deciding whether a consistent layer ordering exists is NP-hard. The difficulty is not in choosing the folds; it is in stacking them.

That result is why this subject looks the way it does. The local theory is elementary and complete; the global theory does not exist, because it provably cannot exist in the form anybody wanted.

What NP-hard does and does not mean

Worth being careful, because the term gets used loosely.

It does not mean particular patterns are hard. The Miura fold is easy; so is a bird base; so is nearly anything a person designs, because designers work in structured families.

It does not mean no algorithm exists. Algorithms exist and work on real patterns. What is ruled out, unless P equals NP, is an algorithm whose running time is polynomial in the pattern size in the worst case.

It does mean there is no clean characterisation waiting to be found. Nobody is going to produce a global analogue of Kawasaki’s theorem, because if they did it would settle a problem in complexity theory.

Why layers are the hard part

The reduction encodes logic into layer ordering, and seeing why that is possible makes the result feel less arbitrary.

Consider two flaps that overlap in the folded state. One is above the other, which is a binary choice. Now consider a chain of overlapping flaps where each pair’s relative order is constrained by the local geometry: the choices propagate, and a cycle of constraints can be contradictory in the same way that “A above B, B above C, C above A” is.

That is enough structure to build logic gates out of. Bern and Hayes construct patterns whose layer-ordering constraints implement a boolean formula, and the pattern folds precisely when the formula has a satisfying assignment.

The elegance of it is also the bad news: layer ordering is expressive enough to encode arbitrary computation, so no simple condition can characterise it.

The smallest sector decidesTwo assignments of the same four creases. Both satisfy Kawasaki and Maekawa. The left one folds; the right one does not, because the strictly smallest sector has the same assignment on both sides and the paper either side of it has nowhere to go.MVMM40°foldsopposite across the small sectorMMVM40°does not foldthe same on both sidesboth satisfy Kawasaki and Maekawa — the angles and the counts are identical
Fig. 3 The last condition that can be checked without thinking about layers. Beyond it the question becomes which sheet lies above which, and that is where the difficulty is.

The one-dimensional case, which is easy

There is a version of the problem that is tractable, and the contrast is instructive.

Take a strip of paper — one-dimensional — with creases at specified points and a mountain-valley assignment. Does it fold flat? This has a polynomial-time algorithm, and the layer ordering can be resolved greedily.

The reason is that a strip’s layers are totally ordered by a single coordinate, so the constraint system is a chain rather than a general graph. Chains do not admit cycles, and it is cycles that make the two-dimensional problem hard.

That gives a clean statement of where the difficulty enters: not in folding, not in the assignment, but in the fact that a two-dimensional sheet’s overlaps form a graph rather than a line.

What is done in practice

Given the hardness, real work proceeds by search rather than by characterisation, and it works well enough.

Layer ordering is set up as a constraint satisfaction problem — variables for the relative order of each overlapping pair, constraints from the local geometry — and solved with a general solver. For patterns of the sizes people actually design, this returns an answer quickly.

That is the ordinary fate of NP-hard problems: the worst case is intractable and the instances that arise are not, because they have structure the worst case lacks. Designed crease patterns are highly symmetric and highly modular, and both properties make the search easy.

Why the checker here is local

This site’s lib/fold.js implements the local conditions and stops, and the choice is deliberate rather than a shortcut.

Implementing a global check would mean a constraint solver, and the result would still not be a proof for patterns of any size. More importantly, it would invite a claim the site should not make. A figure captioned “this pattern folds flat” on the authority of a solver that timed out is worse than one that says what was actually checked.

So the check is local, the assertion is local, and the essays say so. What the site guarantees is that no pattern here fails a condition that can be checked exactly — which is a real guarantee and a bounded one.

How many assignments actually foldFor a fixed set of crease lines, the number of mountain-and-valley assignments that satisfy the local conditions, against the number of assignments there are. The valid ones are a small and shrinking fraction, which is the quantitative form of the claim that flat-foldability is rare.one degree-4 vertex4 of 164 creases · 25.0% surviveone degree-6 vertex8 of 646 creases · 12.5% survivethe preliminary base112 of 2568 creases · 43.8% surviveand these are only the local tests — a pattern can pass every vertexand still collide once the layers stack, which is the hard part
Fig. 4 The local conditions doing what they can. They remove most assignments cheaply and exactly; what remains is a candidate set, and narrowing it further is where the hardness lives.
The Miura foldA grid of identical parallelograms. The assignment is the whole trick: the horizontal creases alternate by row, and the vertical ones change assignment every time they cross a row, so each vertex ends up three of one and one of the other rather than two and two.at every vertexthree of one, one of the other15 interior vertices, all identicalwhat the sheet gainsone degree of freedom, not manyit opens and closes in both directions at oncea negative Poisson's ratio22 mountain and 16 valley creases · 39.3 sheet-widths of foldingmountainvalleyraw edge
Miura fold — sheet 170×106.83 mm — 22 mountain, 16 valley, 1049.4 mm of crease
Fig. 5 A pattern that does fold, and whose vertices are all identical. Structured patterns like this are why the intractable general case rarely bites in practice.

The pattern repeats across the subject, which suggests something structural rather than accidental.

Map folding. Given a rectangular grid with a mountain-valley assignment, can it be folded flat along the grid lines? This is the simplest-sounding question in the field and its complexity was open for decades; the general case is now known to be hard.

Simple foldability. Can a pattern be folded by a sequence of simple folds — each one folding everything along a single line? Also hard in general, and tractable for one-dimensional strips.

Optimal packing. Circle packing for design has no known efficient optimum either.

Three natural questions, three intractability results. The subject is easy locally and hard globally almost everywhere anybody looks.

The preliminary baseBoth diagonals and both midlines of a square, with the assignment that folds flat. Eight creases meet at the centre in equal sectors, so Kawasaki is satisfied by any assignment and Maekawa is the binding condition — five of one and three of the other, never four and four.at the centre8 creases, all sectors 45°3 mountain, 5 valleydifference 2 — Maekawa holdsfour and four would fail,which is what most people drawfold every line, then collapse — the four corners meetmountainvalleyraw edge
Preliminary base — sheet 150×150 mm — 3 mountain, 5 valley, 724.26 mm of crease
Fig. 6 A pattern small enough that every assignment can be enumerated. Scale that up and the enumeration is the thing that becomes impossible.

Where the model stops

Worst case, not typical case. The hardness result is about adversarial patterns. Nothing on this site, and nothing anybody designs, is adversarial.

The reduction is a construction. The patterns Bern and Hayes build to prove hardness are elaborate and artificial. They are proofs, not examples of anything a folder would meet.

Flat-foldability only. Rigid-foldability is a different question with its own complexity, less well characterised.

No thickness anywhere. All of this is about a zero-thickness sheet. Real material adds constraints the theory does not model.

The figure shows a pattern that does fold. It is drawn as an illustration of “every vertex passes”, and it happens to be a Miura, which is genuinely foldable. A pattern that passes locally and fails globally would be a better illustration and would be an artificial construction rather than anything meaningful.

What a designer does about it

The hardness result sounds like it should stop the field and does not, and the reason is that designers never meet the hard cases.

A designed crease pattern is highly structured. It has symmetry, it is built from repeated components, and it comes with a folding sequence that its author already carried out. The layer ordering is not being discovered from scratch — it was determined constructively while the model was being made.

So the practical procedure is not “given a pattern, decide whether it folds”. It is “given a folding sequence, record the pattern”, and the second direction is easy. A crease pattern published in a book is a pattern somebody has already folded, and its foldability is established by demonstration.

The hard direction matters for two purposes. It matters for verification — checking a pattern that somebody derived computationally rather than by folding. And it matters for search — asking whether a pattern with certain properties exists at all, which is what design algorithms do. Both are recent, and both are where the intractability actually bites.

The shape of the field

Stepping back, the subject has an unusual profile, and this result is why.

The local theory is complete, elementary and beautiful. Three conditions, all checkable by arithmetic, a linear-time algorithm, and a clean proof of sufficiency. It could be taught to a bright sixteen-year-old in an afternoon.

The global theory is a hardness result and a collection of special cases. There is no characterisation, there will not be one, and the working tools are constraint solvers.

That combination — elementary local structure, intractable global structure — is not rare in mathematics, and it is unusually stark here because the two are so close together. One vertex is easy. Two vertices are already the general problem in miniature, because two vertices can disagree about layer order. There is no gentle gradient between them.

How many assignments actually foldFor a fixed set of crease lines, the number of mountain-and-valley assignments that satisfy the local conditions, against the number of assignments there are. The valid ones are a small and shrinking fraction, which is the quantitative form of the claim that flat-foldability is rare.one degree-4 vertex4 of 164 creases · 25.0% surviveone degree-6 vertex8 of 646 creases · 12.5% survivethe preliminary base112 of 2568 creases · 43.8% surviveand these are only the local tests — a pattern can pass every vertexand still collide once the layers stack, which is the hard part
Fig. 7 The local conditions, doing what they can. They are exact, cheap and complete for what they measure, and what they measure is one vertex at a time.

What this site does about it

The checker in lib/fold.js is local by design, and the reasoning is worth stating because it is a choice rather than a limitation to apologise for.

A global check would require a constraint solver, would be slow, and would produce a result that is still not a proof for a pattern of any size. It would also invite a claim the site should not make — “this pattern folds flat” on the authority of a search that did not time out.

What the site guarantees instead is bounded and exact: no pattern here violates a condition that can be checked exactly. Every figure has been through developability, Kawasaki and Maekawa and big-little-big, and the assertion throws rather than warns.

For the patterns actually drawn — the preliminary base, the Miura fold, single vertices — that is a complete answer, because those are all cases where the local conditions happen to be sufficient. For anything larger it would not be, and the site does not draw anything larger.

The result is a relief, not a disappointment

An attitude worth ending on, because “NP-hard” reads as bad news and in this case is not entirely.

Before 1996 it was reasonable to hope for a global characterisation — some condition on a whole crease pattern, in the spirit of Kawasaki’s, that would settle flat-foldability by inspection. People looked for one.

The hardness result closed that off, and in doing so it explained the previous decade of failure. Nobody had missed a simple criterion; there is no simple criterion, and the search could stop.

It also redirected the effort productively. Once the general problem is known to be intractable, the useful questions become: which restricted families are tractable, what do designed patterns have in common that makes them easy, and how well do constraint solvers do in practice. All three have yielded results.

That is the ordinary value of a hardness proof. It does not solve the problem; it tells everybody which problem to work on instead.

Two vertices are already the hard case

The sharpest way to state the result is to notice how quickly it arrives.

One vertex: completely solved, three conditions, a linear-time algorithm, a proof of sufficiency.

Two vertices sharing a crease: the two impose layer orderings on the region they share, and the orderings must agree. That agreement is not implied by either vertex’s conditions, and checking it is already outside the local theory.

Many vertices: the agreement conditions form a constraint graph, the graph can contain cycles, and cycles can be unsatisfiable. That is the NP-hardness.

So there is no gentle progression from easy to hard. The whole difficulty is present at two vertices and merely becomes expensive at many. That is why no intermediate theory exists — there is no regime between the vertex conditions and the general problem for one to describe.

What is checkable, and what is claimed

A closing statement of the site’s position, because this essay is where it matters most.

Every crease pattern here has been checked against developability, Kawasaki and Maekawa and big-little-big, at every interior vertex, and the check throws rather than warns.

For the patterns actually drawn — single vertices, the preliminary base, the Miura fold — that is a complete answer, because those are cases where the local conditions happen to settle it.

For a general pattern it would not be, and the site does not draw one. That is a deliberate scoping decision rather than an omission: a figure captioned “this folds flat” on the authority of a search is a different kind of claim from one backed by an exact check, and mixing the two would make the guarantee meaningless.

So what is promised is bounded and true. Nothing here fails a condition that can be checked exactly, and nothing here relies on a condition that cannot.

The positive results

A page about intractability should say what is known, because the field is not stuck.

Single vertices are completely solved, with a linear-time algorithm.

One-dimensional strips are solved, and the algorithm is greedy.

Simple foldability — folding by a sequence of single straight folds — is decidable for one-dimensional cases and understood for several restricted two-dimensional families.

The fold-and-cut theorem is a striking positive result in the same territory: any plane graph of straight lines can be cut out with a single straight cut, and the construction is effective. That one goes the other way entirely, turning an apparently impossible request into an algorithm.

Map folding for small grids is settled by exhaustive enumeration, and the counts are known for grids up to a useful size.

So the picture is not a wall. It is a boundary, with a well-explored tractable side and a set of techniques for getting useful answers on the other, and the boundary itself is now understood well enough to know which side a new question falls on.

The ladder from here

Later rungs: the Bern and Hayes reduction. Layer ordering as a constraint problem. One-dimensional flat-foldability and its algorithm. Map folding, and why it stayed open so long. Simple foldability. The fold-and-cut theorem, which is a positive result in the same territory. Constraint solvers in practice. Structured families where the problem is easy. And the question of what makes designed patterns tractable, which is understood informally and not formally.

The single-vertex problem was solved completely in about a decade. The global problem was proved impossible to solve cleanly in roughly the same decade, and both results are from the 1990s.

Where this goes next

VMMM60°90°120°90°Kawasaki60° + 120° = 180°90° + 90° = 180°both 180° — satisfiedMaekawa3 mountains, 1 valleysdifference 2exactly 2 — satisfiedangles sum to 360°which is what a flat sheet requiresmountainvalley Two conditions at a point Whether a single vertex folds flat is decided completely by two tests — one on the angles, one on the assignment. They are independent, they are easy to check, and together they settle the case entirely. MVMM40°foldsopposite across the small sectorMMVM40°does not foldthe same on both sidesboth satisfy Kawasaki and Maekawa — the angles and the counts are identical The smallest sector decides Two assignments can satisfy both flat-folding theorems and only one of them folds. What separates them is a condition about the smallest angle, and it is the first rule in the subject that is not about counting. leglegarmarmheadthe checkclosest approach 0.0000no overlap — the packing is validcircles use 71% of the sheetthe rest becomes the bodyefficiency is how much of thesquare the circles can claim,and it is an open problemthe dashed skeleton is the subject; the circles are what it costs Packing is the hard part Once a subject is a set of circles, designing the model is fitting them into a square. That step has no general algorithm, no known optimum, and it is where every remaining difficulty in origami design now sits.