Probably the best theory in the world

If it takes ten seconds to sort five cards, how long will it take to sort 50 cards? The answer, of course, depends on the method used.

If you are systematic and use the same procedure in each case, the chances are it will take 100 times longer, more than 15 minutes. In fact, even if you know all the tricks of fast sorting, you can be sure it will still take at least four minutes.

The theory which tells us this is complexity theory, the theory of the resource requirements, especially time and space, of algorithms and problems. Complexity theory is a young field that sprouted from theoretical concerns with efficiency in the first medium sized digital computers.

Texts within this field are few and far between, and this introductory text by Daniel Pierre Bovet and Pierluigi Crescenzi is long overdue. It is the latest addition to the Prentice Hall International Series in Computer Science, and an admirable addition to an excellent series it is. The book is admittedly difficult, but the topic is not easy.

The way that complexity theory goes about studying the resource requirements of problems is to group them into equivalence classes. Some problems, such as the sorting task above, are easy. Easy problems form a natural class, P, the class of problems solvable in time proportional to some polynomial function of the size of the input. Other problems are easy given some lucky guesses. These also form a natural class, NP, the class of problems solvable by a non-deterministic machine in polynomial time. There are many further classes, classes for more time-consuming problems, and classes based on space requirements, but the real question in complexity theory concerns the identity of the first two classes, P and NP. Are they the same?

It is conjectured that they are not, that there is no way of reducing a problem that can only be solved quickly with guessing to an equivalent problem which can be solved quickly without guessing, but this conjecture has resisted all attempts at proof since it was first formulated in 1972.

Within the domain of complexity theory, the conjecture has almost the status of Fermat's last theorem. In bringing together 25 years of research, this text presents numerous tantalising results which bear on the conjecture, but the results presented are troublesome, for although they indicate that the conjecture is intimately related to a number of other results, all of which stand or fall together, informal meta-reasoning suggests that no current proof techniques will be able to resolve the question, either positively or negatively.

Apart from the classification of problems, complexity theory is also about proving relationships between the various theoretical problem classes. Proof techniques are important, so it is reassuring to see that every theorem mentioned in this book is followed by its proof. The proof techniques peculiar to complexity theory are thus amply illustrated.

As a young field, complexity theory is a field of active research. In their last few chapters Bovet and Crescenzi explore some of the more recent research issues in complexity theory. Topics covered include approximation (if the exact solution to a problem cannot be found quickly, can we find a fast approximate solution?), probabilistic algorithms (can we find fast algorithms for difficult problems that give correct answers most of the time?), and parallel algorithms (what sort of problems will gain most by technological advances in parallel computing?).

These chapters provide a good insight into what current research into complexity is about, and add to the impression which the book gives of being at the cutting edge of the field.

As with any difficult mathematical topic, the difficulty within complexity theory lies in fully understanding the basic concepts. Given this, the only criticism that could realistically be levelled at this work is that insufficient space is devoted to the basic concepts. While Bovet and Crescenzi give informal intuitive explanations of some of the more difficult theorems that they consider (and they consider a vast number of theorems), they do not provide such intuitive background information for many of the more fundamental concepts.

It is for this reason that the word "introduction", in the title, might be considered an overstatement. Though it is well written, this book is not for the faint-hearted. It may serve as an advanced undergraduate text, but it will find a more appropriate home with postgraduates. It is, however, more than just a text.

It is an up-to-date compendium of results. With detailed references notes and a bibliography of more than 200 references, this introduction to the theory of complexity will serve for many years as a useful reference.

Dr Richard Cooper is a research fellow, department of psychology, University College London.