NP-Completeness and Origami

NP-complete problems are defined by their computational complexity, which measures how the work involved in solving a problem relates to the size of the problem itself. For example, when you add two n-digit numbers, you start at the right and add each pair of digits (plus any carries), record the result, and go on to the next pair. You do this n times and thus the problem’s complexity is said to be of order n, abbreviated as O(n).

For simple addition, complexity increases linearly, but often it grows much faster. For example, you “convolve” two lists of numbers by multiplying every number in one list by every number in the other list and then adding them up in groups. (Convolution is what Adobe Photoshop does when it blurs or sharpens an image.) For two lists of n numbers, there are n2 multiplications and n2 additions, so the problem is said to be O(n2). Now, if you double the problem’s size, you quadruple the program’s running time.

Sometimes there are faster approaches. While multiply-and-add is O(n2), the Fast Fourier Transform allows you to do a convolution in O(n log n), meaning that the number of steps is proportional to the product of n and its natural logarithm. Of course, n log n still grows, but much more slowly than n2. A fast algorithm can make the difference between minutes and days of computing.

Addition and convolution are called class P problems, where P stands for “polynomial time,” because the time needed to solve them is bounded by some finite polynomial in n (meaning n raised to a finite power; thus, n log n is bounded by n2).

But a host of nasty problems appear to scale as an exponential of their size and quickly become intractable as n increases. Running an exponential-time algorithm might easily take longer than the age of the universe even for fairly small values of n.

One famous example is the traveling salesman problem: given the locations of n cities, what is the shortest route that visits each city? A related form of the problem asks if there is a route shorter than a specified distance. Although people have figured out relatively fast ways of finding pretty good answers—routes that are among the shortest—the only known way to guarantee you’ve really found the shortest one is to compare all possible routes, or at least a fairly large subset of them. The traveling salesman is in a class of problems, called NP for “nondeterministic polynomial time,” which may or may not be solvable in polynomial time, but whose solutions, once found, can be checked in polynomial time. For example, it’s easy to see whether a route is under 100 miles long.

The traveling salesman problem and several others are in a special corner of NP, called NP-complete, which means that they are hard in a particular way. As in the case of convolution, problems can sometimes be converted, or “reduced,” to other problems. NP-complete problems have the property that every problem in NP can be converted into any NP-complete problem, which means that if you could knock off one of these incorrigibles in polynomial time, you could use the same approach to solve all NP problems and make millions of dollars along the way. The frustrating thing is that although almost everyone believes that there are no polynomial-time algorithms for NP-complete problems, no one has been able to prove it.

Which brings us to an origami problem: given a pattern of creases, how can you assign valley and mountain folds to the creases so that the result can be folded flat? It’s pretty easy to analyze a single vertex where creases intersect. For example, if four creases come together, they will only fold flat if there are three mountain folds and one valley fold or vice versa, and the sums of opposite angles are equal. (To see this, fold a square in half and then in half again to make a new square one-fourth the original size.)
The complexity arises when edges and layers start to collide in a large pattern. You can’t pass the paper through itself, and a crease that runs all the way across the paper can make widely separated regions interfere with one another. Such long-range interconnectedness is a hallmark of the traveling salesman problem and its ilk.

Bern and Hayes showed that assigning mountain and valley folds is equivalent to the so-called “not-all-equal three-variable satisfiability” problem, which is known to be NP-complete: given a collection of clauses, each containing exactly three true-false logic variables, determine whether you can make each clause have either one or two, but not zero or three, “trues.” A simple example is shown in the margin. Bern and Hayes converted the clauses into small crease patterns connected by long, skinny pleats. A noninterfering set of mountains and valleys corresponded to a valid set of trues and falses. So a pleat that went mountain-valley might mean “Pat is the husband, Kim is the wife,” whereas valley-mountain would mean “Pat is the wife, Kim is the husband.” Thankfully, only one particular class of crease-assignment problems is NP-complete, or this article would not have been written.

As noted earlier, if you could solve one NP-complete problem efficiently, you’ve solved them all, but proving that a problem is NP-complete does not prove that no efficient algorithm for solving it exists. It just means that while I can’t find one, neither can all the famous folk.