Labyrinths of Reason (29 page)

Note why this is easier. Whenever it is possible to answer the eternal question (by specifying a route), it is simplicity itself to answer the existential question: The answer is yes. Even when it is
not possible to specify a route, there may be circumstances where it can be demonstrated that a simple path exists. It is only to be expected that a yes-or-no question would be easier than a question whose answer might (for all we know) entail tedious directions for a route billions of branches long.

Only skeptics ask the existential question. It is an article of faith with most explorers of the maze that all points are connected somehow, that you can always get there from here. Long and tortuous though the route may be, it exists. This need not be so. The labyrinth may not be fair; it may pose questions that have no answer. There could be two intertwined but distinct networks of paths, with no way of crossing from one to the other. There could be trillions of separate networks. Even allowing that the maze is a single network, local knowledge of the labyrinth can never demonstrate this. It remains conceivable that there is no way of getting to a desired point, up until the time that a specific route is found and verified.

The “existential question” is really an NP-complete problem called the LONGEST PATH problem. NP-complete problems are notoriously “difficult,” yet the existential question is sometimes easily answered. Say that point G happens to be a single branch away from E. Then casual exploration would find G almost immediately—answering both the existential and the eternal question.

Nothing wrong there. Specific instances of a general problem may be quite easy. What is sought is a general, systematic method of answering the existential question that would work in the smallest maze or in an infinite labyrinth.

There is no fast way of solving an unknown maze, no way of knowing, presciently, which paths to favor. The best one can do is to examine nearly
all
paths until the goal is found. The various maze algorithms only prevent one from repeating the same branches unknowingly or from wasting further time with known cul-de-sacs and loops. The algorithms cannot guide you “intelligently” through untrod regions of the labyrinth.

Look at the Ore algorithm, as efficient as any. You start from the home node. Three branches lead from this node. Each neighbor node is connected to two other nodes. (One of the three branches is the one connecting the neighbor node to the home node, which has already been considered.) In turn, each of the six nodes once removed is connected to two more nodes. The maze is hydra-headed. Branches you explore lead to new nodes from which spring yet more branches. Some of these branches may have been explored previously (as evidenced by old trail markers). Much of the time,
the number of branches to be explored mushrooms exponentially. The more you know about the labyrinth, the more you realize you don’t know.

If you can explore a branch a minute, the progress of the Ore algorithm looks like this:

In all finite labyrinths, the process of discovering new branches must eventually come to an end. Past a certain stage in the exploration, most new branches will lead back to familiar nodes. Finally, all the branches will have been traversed, and the goal must be known. In the infinite labyrinth, the exponential spiral continues forever. Even when the goal is relatively nearby it can take impracticably long to find it. It would take all day to find a goal five nodes away, though the route itself, once known, could be traversed in five minutes. The search for a goal fifteen nodes away would take years, and not all the time in the universe would be adequate to find a goal just forty-five nodes distant.

Look at the LONGEST PATH problem from the point of view of a computer programmer. You want a computer to decide whether there is a route connecting two points in a certain large labyrinth. To do this, you must give the computer a “map” of the maze. This map takes the form of a list of all the nodes in the maze and a list of all the branches. The nodes are numbered or named; the branches are specified by indicating which nodes they connect and the distance (an integer expressing the distance in whatever units desired) between them. One branch might be listed as “Node 16, Node 49: 72 feet.” The distance is the actual length of path a wanderer would cover, not straight-line distance. The two nodes that are the entrance and the goal are specified as such.

There is a further element to the LONGEST PATH problem, a specified distance,
n
. The LONGEST PATH problem asks whether there is a direct path between entrance and goal
longer
than
n
units of distance. If you like,
n
can be arbitrarily small or zero. In that case the LONGEST PATH problem asks whether there is a path longer than zero length—that is, whether there is any path whatsoever—between entrance and goal.

Since the existential question is NP-complete, the more difficult eternal question is at least as hard as the NP-complete problems. If it is impracticably hard even to say if a route to G
exists
, then it is also impracticable to specify such a route.

The NP-complete problems have the surprising property that their answers are easily verified. You meet an oracle who has the ability to divine the answer, instantly, to any question at all. Those who believe in the oracle’s omniscience come to him with questions so difficult that no one else can solve them, and he answers them immediately.

Yet he is frustrated in his attempts to prove his power to
everyone
. There are skeptics. The oracle wants to prove his omniscience is genuine by showing that the answers he gives are correct. This is not always possible.

He receives two types of questions. The most common type comprises difficult questions that no one else can answer. Why is there evil? Does God exist? What is the googol-th digit after the decimal point in the decimal expansion of pi? It so happens that the oracle’s answers to these questions are correct and accurate in all respects. But he is unable to prove these answers. As the skeptics sneer, he could pretty much give any answer to these problems, and no one would be the wiser. Even the relatively down-to-earth questions (such as about the googol-th digit of pi) may be so difficult that the most powerful computer in the world cannot verify his answers.

To prove his powers, the oracle must answer questions whose answers can be checked. He gets many of these questions too, some from skeptics trying to show him up. What is the capital of Kiribati? What’s the square root of 622,521? Name the sisters in
Little Women
. Here’s a sealed box: What’s in it?

The oracle answers each of these questions correctly, and the poser knows that he’s answered correctly. The poser knows that because he knew the answers all along. That’s the trouble. These
questions are too easy to prove the oracle’s powers beyond all doubt. If the person asking the questions already knew the answers by ordinary means, then conceivably the oracle knew or found out the answer by ordinary means too. His clairvoyance could be an act, the skeptics say; he could be nothing more than a calculating prodigy, well versed in trivia, who employs the paltry deceptions of the stage mind reader for the rest.

The oracle loses either way. Answer a question that no one else possibly could, and he is accused of fabricating; answer a question whose answer is known or knowable, and he is accused of cheating. To prove his omniscience, he needs a third type of question—a
difficult
question whose answer, once stated, can be verified
easily
. Are there questions like that?

Questions about the infinite labyrinth qualify. Let skeptics pick two random points in the labyrinth and ask the oracle to specify a route between them. Anyone can easily assure himself that an answer is correct (or incorrect). All they have to do is follow the prescribed route and verify that they end up at the right point.

Wouldn’t this be another “easy” question? It is necessary to make sure that the two chosen points are far enough apart so that no one knows a route connecting them, or even could find such a route by normal means. The relative inefficiency of even the Ore algorithm guarantees that such pairs of points are common. If the points are twenty nodes apart, it would take centuries to find a path by ordinary means. Then wouldn’t it be another “hard” question? No, because it would only take about twenty minutes to verify the oracle’s answer (traversing a branch a minute). A maze’s solution is much, much simpler than the maze itself.

This third type of question is close in spirit to what complexity theorists mean by the “class NP.”

There is a distinction between a problem in general and
instances
of a problem. A jigsaw puzzle is a general type of problem; a specific jigsaw puzzle with 1500 pieces that fit together to make a picture of a Dutch windmill is one instance of the problem.

The theory of NP-completeness judges the difficulty of problems not by any particular instance of the problem, but rather by the way the difficulty grows as a function of the size of the problem. In the case of a jigsaw puzzle, the “size” of a puzzle is the number of pieces. The more pieces, the harder the puzzle is. How “hard” the
puzzle is is best measured by the time it takes to solve it. This depends on how fast you work, of course, but it clearly has a lot to do with how many pieces must be compared against other pieces to find a match.

In a worst-case jigsaw puzzle—such as one of those novelty puzzles that are all one color—you have to compare pieces randomly to see if they fit. In the early part of the process, you end up comparing each piece against a large fraction of the other pieces. The total number of distinct matching operations is proportional to the
square
of the number of pieces. Therefore, the time requirement can be expressed as a polynomial function containing
n
²
, where
n
is the number of pieces.

This time requirement is relatively modest. In a maze, the time required to find the goal using the Ore algorithm is more like 2
ⁿ
, where
n
is the number of nodes to the goal. When
n
is small, the difference between
n
²
and 2
ⁿ
is not great. As
n
increases, a chasm opens up between the polynomial and exponential functions. You can solve a jigsaw puzzle with 5000 pieces. You cannot solve a nontrivial maze requiring 5000 correct turns to find the goal.

The “easy” problems of complexity theory are those general problems that may be solved in polynomial time. These problems form the class P (for polynomial). Think of class P as a vast country somewhere, poorly mapped, yet with distinct boundaries. Every point is either in P or not, though our maps are so unreliable that it is not always possible to say which. Jigsaw puzzles are one point in class P; so are simple arithmetic problems.

There is another class of problems, NP, including all those problems whose
solutions
may be
verified
easily (in polynomial time). When a problem is easy, its solution is easy to check too. If nothing else, you can check it by solving the problem all over and making sure you get the same answer. So all easy problems (class P) are in the class of problems whose answers are easy to check (NP). NP also includes many problems not in P, such as solving mazes. P is thus a province of the larger country NP. If we were to draw a map, it would look like the diagram on the opposite page.

The outer rectangle represents all possible problems. The class NP does
not
include all problems. There are ultra-hard problems whose answers cannot even be checked easily. These are represented by the region of the rectangle outside of NP’s circle.

Put this in the context of the oracle’s questions. The first class of questions, “hard” questions that cannot be checked, are analogous to the class of problems outside of NP. The second type of questions
corresponds to the class P. The third class—hard questions with easily verified answers—corresponds to those problems in NP but outside of P.