There are two theorems about flat origami that you can learn in twenty minutes. Together they tell you whether a single vertex in a crease pattern can fold flat. Neither one tells you whether the whole sheet folds flat. The gap between those two statements is an NP-complete problem.
Maekawa's theorem: at any flat-foldable vertex, the number of mountain folds and the number of valley folds must differ by exactly two. The proof takes one sentence. As you trace a closed loop around the vertex, each mountain fold rotates you by π and each valley fold rotates you by −π. To close the loop you need a total rotation of ±2π. So M − V = ±2. That's it. A vertex with four creases has either three mountains and one valley, or one mountain and three valleys. No other combination works.
Kawasaki's theorem: at any flat-foldable vertex, the alternating sum of the angles between consecutive creases equals zero. If the angles going around are α₁, α₂, α₃, … α₂ₙ, then α₁ − α₂ + α₃ − … − α₂ₙ = 0. Equivalently, the odd-indexed angles sum to π, and so do the even-indexed ones. The crease count must be even — a vertex with an odd number of folds cannot fold flat under any assignment.
These two conditions together are necessary and sufficient for a single isolated vertex. But crease patterns have many vertices, and the conditions interact. A valid assignment at one vertex may force an impossible assignment at a neighbor. You can construct crease patterns where Kawasaki and Maekawa are satisfied at every vertex, individually, and the whole sheet still cannot fold flat — the constraints that ripple between vertices create a contradiction the local rules didn't detect.
Determining whether a given crease pattern has any valid global flat folding is NP-complete. This was proved by Marshall Bern and Barry Hayes in 1996. The reduction goes through 3-SAT: you can encode logical variables and clauses into crease patterns such that the pattern is flat-foldable if and only if the corresponding Boolean formula is satisfiable. So any efficient algorithm for origami flat-foldability would solve an NP-complete problem. There probably isn't one.
What I find worth sitting with is the texture of this gap. The local conditions are elegant — they have short proofs and clean geometric interpretations. They're the kind of result that makes you feel the problem is basically solved. And then the global question is intractable, and the same structures that make the local conditions easy to state are what make the global problem hard: mountain-valley assignments propagate constraints through the sheet in ways that interact combinatorially.
There's a separate surprise, unrelated to hardness, about what paper folding can compute. Classical compass-and-straightedge construction is limited to the square roots — you can bisect angles, construct square roots, solve quadratic equations. Angle trisection is impossible with those tools. With origami it isn't. The Abe trisection fold solves a cubic. The six Huzita-Hatori axioms — the complete set of distinct fold operations — let you solve arbitrary cubic equations, which is strictly beyond compass-and-straightedge. Some researchers have claimed extensions into the quintics; the boundaries there are still being mapped.
Robert Lang's TreeMaker software takes this further: given a tree structure representing the limbs and appendages of an origami figure — a beetle with six legs, two antennae, wing cases — it finds a crease pattern that produces a base with exactly those proportional extensions. The algorithm treats the tree as a packing problem: each leaf of the tree corresponds to a circle on the paper, and the circles must be packed without overlap while respecting the metric constraints of the tree. The crease lines are then derived from the circle arrangement. Finding the optimal packing is itself a nonlinear constrained optimization, which Lang solved using Lagrangian methods he'd encountered at JPL. The meeting of paper folding and satellite engineering happened to be useful in both directions.
The thing that stays with me is not the hardness result or the cubic-solving capability — it's the shape of the knowledge. Two theorems that work perfectly at a vertex. A third question, about the whole sheet, that they can't answer. The local conditions are complete where they apply. They just don't apply to the thing you're actually asking about.
This pattern comes up in a lot of places. Necessary conditions that are locally tight but globally blind. The interesting mathematics is often in the gap.