Labyrinths of Reason (27 page)

In Western tradition, the most famous maze is the Minotaur’s labyrinth on the Greek island of Crete. In Greek legend, the Minotaur, a monster with human body and bull’s head, inhabited the center of a vast maze designed by Daedalus for the Cretan king Minos. After Crete’s defeat of Athens, Minos decreed that the citizens of Athens sacrifice seven young men and seven young women to the Minotaur every nine years. None of the youths who entered the Minotaur’s labyrinth ever made their way out. The Athenian prince Theseus volunteered for the sacrifice. Minos’s daughter, Ariadne, advised him to let out a silken thread as he entered the maze so that he would be able to find his way out. In this way Theseus slew the Minotaur and ended the tribute.

The legend may have evolved from travelers’ tales of Athenians sent to Crete to pay tribute during the height of Minoan sea power. Maybe they saw something in Crete they didn’t understand (a mystery-cult priest wearing a bull mask?), and the story became garbled. It is unknown whether, or in what form, a labyrinth existed in ancient Crete. In the Cretan language, a labyrinth could mean a mazelike building, a grotto or winding cave (a common feature of the Cretan landscape), or an inescapable dilemma in argument: a paradox. After Cretan civilization ebbed, the ruined palace at Knossos was called a labyrinth, perhaps only in sardonic comparison to a rock cave. Surviving coins of Knossos show the plan of a maze that
seems to be an architectural labyrinth, not just a natural cave. Archaeologists discovered the remains of the palace at Knossos early in the twentieth century, but nothing resembling a labyrinth was found.

Another maze shrouded in legend is Rosamond’s Bower, supposedly built in a park at Woodstock, England, in the twelfth century. The impenetrable maze concealed King Henry II’s mistress, Rosamond the Fair (c. 1140–c. 1176), from his wife, Eleanor of Aquitaine. Henry found his way to a hidden trysting place aided by a secret “key” that revealed the route. According to legend, Eleanor found her way to the center of the maze trailing string and made Rosamond drink poison. This story did not appear until the fourteenth century and is apocryphal. It is not even certain that Rosamond’s Bower existed, or if it was a proper maze in the modern sense. Less romantic historians suspect it was only a poorly designed house with confusing passages.

The modern “labyrinth” is almost always a garden maze of paths bounded by hedges of (in Britain) hornbeam or yew. British garden mazes flourished during Tudor and Stuart times. Maze designers often incorporated a key, a clandestinely marked route of egress, so that the initiated could find their way in and out without difficulty.

The labyrinth remains mysterious. The problem of threading a maze is NP-complete: one of a set of universal problems with the potential to confound the most powerful of computers.

The world is a labyrinth of madly interlocking connections and relationships. One idea that expresses this goes by the blandly understated name “NP-complete.” For the record, “NP-complete” stands for “nondeterministic, polynomial-time-complete.” Those daunting words name a fundamental and universal kind of problem—one rich in practical and philosophical significance.

NP-complete is a class of problems that have been haunting computer programmers for three decades. Computers have been getting faster and more powerful ever since their invention. The computers of the late 1980s are roughly 30,000 times faster than the computers of the late 1950s. One boast goes: “If automobile technology had advanced at the same rate as computer technology, a Rolls-Royce would travel at supersonic speed and cost less than a dollar.” By the mid-1960s, however, computer scientists began to realize that something was amiss. Certain common problems are extremely difficult
to solve by computer (or by any known method). Throwing faster processors or more memory at them doesn’t make nearly as much of a difference as might be hoped. These problems came to be called “intractable” or “intrinsically difficult.”

One example is the “traveling salesman” problem, which appears in many old puzzle books. A mathematical riddle, it asks you to find the shortest route for a salesman who must travel to several cities, given the distances between the cities. The problem taxes the power of the largest computers. The catch is combinatorics, the stupendous number of combinations of a not so large set. The best ways known of solving the problem are not that much faster than adding up the mileage for every possible routing. The amount of arithmetic to be done mushrooms as the number of cities increases, and quickly outstrips the capacity of any conceivable computer.

The class of NP-complete problems was first explicitly described in a 1972 paper by Richard M. Karp of the University of California at Berkeley. Since then NP-complete has reared its head in dozens of unexpected areas. Many children’s riddles, puzzles, games, and brainteasers are instances of NP-complete problems. It almost seems that a short problem has to be NP-hard to provide much of a challenge. Research into NP-complete problems has often been vigorously funded, by the standards of theoretical research, because of the enormous economic value. Virtually any industry that does computer modeling, from oil production to integrated circuit design, faces NP-complete problems. Finding an efficient “solution” to the NP-complete problems (deemed unlikely by most computer scientists) would be worth many billions of dollars. There is no more poignant illustration of the information age than that much of the military security of the United States, the Soviet Union, and other technologically sophisticated nations is now perched precariously on NP-complete. The “public key” ciphers that protect the superpowers’ sensitive data are founded on the practical insolubility of large NP-complete problems. Similar ciphers promise to ensure privacy of personal data in business and governmental data bases. The discovery of the equivalence of so many diverse problems is intriguing from a philosophical viewpoint too. It is little wonder that “few technical terms have gained such rapid notoriety as the appellation ‘NP-complete,’” as Michael R. Garey and David S. Johnson began their influential 1979 book
Computers and Intractability: A Guide to the Theory of NP-Completeness
.

NP-cbmpleteness is such a slippery abstraction that it is well to describe it with a concrete symbol. A labyrinth is more than a
metaphor for our quest for knowledge; it is (from a suitably abstracted perspective) methodologically equivalent to our logic. Mazes prefigure the essential problem of deduction, that of finding a paradox.

Let’s approach NP-completeness by asking this: Is there a general method that will solve any maze?

Yes; there are several methods, in fact. Not all mazes are puzzles. A
unicursal
maze is one with a single unbranching path from beginning to end. You can’t make a wrong turn. Many medieval mazes were convoluted but unbranching paths leading to a tree or a shrine. Early British churchyard mazes of this type symbolized the tortuous path of the pious through the wickedness of the world. Pilgrims traversed some mazes on their knees. At each turn of the maze, the pilgrim might have said
pater
or
ave
.

It is possible that the Minotaur’s labyrinth at Knossus was unbranching. The coin design shows an unbranching path. If you met the Minotaur in such a maze, you would have only to do an about-face and run; you could never find yourself backed into a blind alley. On the other hand, the coin may show a stylized motif and not a literal map; or the design may have represented the correct route to take in a more complex network of paths. Using a silk thread to find the way out makes no sense unless there were branching paths.

Every maze has at least one entrance, and most have a goal, a point in the maze you try to find. The goal is usually near the maze’s center, though it may be simply an exit on the maze’s perimeter (as in amusement-park halls of mirrors). To solve such a maze is to find a route from entrance to goal. There may be just one route, or many. When more than one route connects the entrance and goal, the implicit puzzle is to find the shortest route.

Some mazes have more than one entrance. They are not fundamentally different from single-entrance mazes. There your first choice is which entrance to use; the fact that this choice is made outside the maze walls does not really change things. There are also multiple-goal mazes where the visitor is expected to visit all parts of the maze, or all of a set of points marked with statuary, benches, or other devices. Louis XIV built a celebrated labyrinth at Versailles in which visitors sought out each of thirty-nine sculptures commemorating Aesop’s fables. A water fountain sprang from the mouth of
each animal that spoke in the fables. Finally, there are undirected mazes where the point is simply to go in, wander around, and find your way out again.

In the geography of mazes, a
node
is a fork, a point where paths meet and you must make a decision. The entrance, the goal, and dead ends are also considered nodes. The segment of path between two nodes is called a
branch
. A simple map of any maze can show the nodes as dots linked by lines representing the branches. A maze is a graph, in the mathematical sense of the term.

Nearly all physical labyrinths are two-dimensional. That means branches never cross. In a three-dimensional labyrinth, bridges and underpasses permit branches to cross over each other like freeway interchanges.

It is one thing to solve a maze from a diagram and another to solve it from within. The eye can often solve the paper mazes of puzzle books at a gestalt. Inside a real maze of hedges or masonry it is difficult to form a mental map. Clever designers may make one junction of branches look so similar to another that you think you’re going in circles even when you aren’t. Nor can you resort to such time-honored paper techniques as starting at the finish and working backward (sometimes this is easier, sometimes not) or marking off dead ends to make the through routes more visible.

The difficulty of a maze has a lot to do with the number of branches leading from each node. When each node is allowed only one branch, the only possible arrangement is a unicursal maze. Represent the nodes as two beads, each connected to one end of a string. No matter how you convolute the string, it leads inexorably from one bead to the other. The maze at Chartres Cathedral is unicursal. It has no walls but is laid out in blue and white marble on the floor.

Nor is there a puzzle when two branches meet at each node. Picture a length of string with a number of beads along its length There is still no choice to make. In fact, normally you don’t even count a “junction” of two branches as a node. It is simpler to think of it as a kink in a single branch.

A real fork in the maze requires at least three paths meeting at a point (the fork’s “handle” and two “tines”). The more branches meeting at a maze’s nodes, the more difficult it is.

By custom, most recent garden labyrinths have an approximately rectilinear design in which substantially all the area is honeycombed with paths and hedge dividers. This makes it difficult for more than four branches to meet at one node. A more flexible design was used
in the labyrinth at Versailles. There branches were not necessarily parallel, and many might meet at a single node. The maximum was five branches at a node. André Le Nôtre, architect of the Versailles maze, built another labyrinth at Chantilly containing a central node where eight branches joined.

The Versailles Labyrinth

The table shows some statistics on several famous labyrinths. In some cases, the number of nodes and branches is open to interpretation. In each case I have tried to count as a node each point where a careful traveler would come to a decision. I counted entrances, goals, and dead ends as nodes, but did not count any superfluous nodes where two branches met. The last column, the average number of branches meeting at a node, is a rough measure of the difficulty of the maze.

The best-known maze algorithm is the “right-hand rule.” Whenever you have a choice, take the rightmost branch. If you come to a dead end, retrace your steps to the last node and take the rightmost of any branches not yet visited. The best way to visualize these rules is to keep your right hand touching the hedge to your right throughout the maze. Never skip over a branch on your right.