- the table of contents,
- the preface to the English edition, and
- the preface to the German edition

You can order this book (or order other books) directly from Springer or check your local academic bookstore.

Fundamental Definitions and Results | 1 | |

1 | The Priority Method | 9 |

2 | Hilbert's Tenth Problem | 15 |

3 | The Equivalence Problem for LOOP(1)- and LOOP(2)-Programs | 25 |

4 | The Second LBA Problem | 37 |

5 | LOGSPACE, Random Walks on Graphs, and Universal Traversal Sequences | 41 |

6 | Exponential Lower Bounds for the Length of Resolution Proofs | 49 |

7 | Spectral Problems and Descriptive Complexity Theory | 61 |

8 | Kolmogorov Complexity, the Universal Distribution, and Worst-Case vs. Average-Case | 71 |

9 | Lower Bounds via Kolmogorov Complexity | 77 |

10 | PAC-Learning and Occam's Razor | 85 |

11 | Lower Bounds for the Parity Function | 91 |

12 | The Parity Function Again | 101 |

13 | The Complexity of Craig Interpolants | 111 |

14 | Equivalence Problems and Lower Bounds for Branching Programs | 115 |

15 | The Berman-Hartmanis Conjecture and Sparse Sets | 123 |

16 | Collapsing Hierarchies | 131 |

17 | Probabilistic Algorithms, Probability Amplification, and the Recycling of Random Numbers | 141 |

18 | The BP-Operator and Graph Isomorphism | 153 |

19 | The BP-Operator and the Power of Counting Classes | 163 |

20 | Interactive Proofs and Zero Knowledge | 175 |

21 | IP = PSPACE | 183 |

22 | P does not equal NP with probability 1 | 191 |

23 | Superconcentrators and the Marriage Theorem | 197 |

24 | The Pebble Game | 203 |

25 | Average-Case Complexity | 213 |

26 | Quantum Search Algorithms | 223 |

Solutions | 237 | |

Bibliography | 317 | |

Index | 321 |

A few of my colleagues had also seen the book. They also found it interesting, but most of them did not read German well enough to read more than small portions of it enjoyably. I hope that the English version will rectify this situation, and that many will enjoy (and learn from) the English version as much as I enjoyed the German version.

The front matter of this book says that it has been ``translated, revised, and expanded.'' I should perhaps say a few words about each of these tasks. In translating the book, I have tried as much as possible to retain the feel of the original, which is somewhat less formal and impersonal than a typical text book yet relatively concise. I certainly hope that the ``pleasure of the pursuit of understanding'' has not gotten lost in the translation.

Most of the revisions to the book are quite minor. Some bibliography items have been added or updated; a number of German sources have been deleted. The layout has been altered somewhat. In particular, references now occur systematically at the end of each chapter and are often annotated. This format makes it easier to find references to the literature, while providing a place to tie up lose ends, summarize results, and point out extensions. Specific mention of the works cited at the end of each chapter is made informally, if at all, in the course of the presentation. Occasionally I have added or rearranged a paragraph, included an additional exercise, or elaborated on a solution, but for the most part I have followed the original quite closely. Where I spotted errors, I have tried to fix them; I hope I have corrected more than I have introduced.

While translating and updating this book, I began to consider adding some additional ``gems'' of my own. I am thankful to Uwe, my colleagues and Hermann Engesser, the supervising editor at Springer Verlag, for encouraging me to do so. In deciding which topics to add, I asked myself two questions: What is missing? and What is new? From the possible answers to each question I picked two new topics.

The introduction to average-case complexity presented in Topic 25 seemed to me to be a completion (more accurately, a continuation) of some of the ideas from Topic 8, where the term average-case is used in a somewhat different manner. It was an obvious ``gap'' to fill.

The chapter on quantum computation (Topic 26) covers material that is for the most part newer than the original book; indeed, several of the articles used to prepare it have not yet appeared in print. I considered covering Shor's quantum factoring algorithm -- either instead or additionally -- but decided that Grover's search algorithm provided a gentler introduction to quantum computation for those who are new to the subject. I hope interested readers will find Shor's algorithm easier to digest after having worked through the results presented here. No doubt, there are many other eligible topics for this book, but one must stop somewhere.

For reading portions of the text and providing various suggestions for improvement, I want to thank Drue Coles, Judy Goldsmith, Fred Green, Steve Homer, Steve Kautz, Luc Longpre, Chris Pollett, Marcus Schaefer, and Martin Strauss, each of whom read one or more chapters. I also want to thank my wife, Pennylyn Dykstra-Pruim, who in addition to putting up with my long and sometimes odd hours also proofread the manuscript; her efforts improved its style and reduced the number of typographical and grammatical errors. Finally, many thanks go to Uwe Schöning for writing the original book and collaborating on the English edition.

Randall PruimJuly, 1998

This book is based primarily on the preparatory materials and worksheets which were prepared at that time for the students of my course and has been subsequently augmented with additional topics. This book is not a text book in the usual sense. In a textbook one pays attention to breadth and completeness within certain bounds. This comes, however, at the cost of depth. Therefore, in a textbook one finds too often following the statement of a theorem the phrase: ``The proof of this theorem would go beyond the scope of this book and must therefore be omitted.'' It is precisely this that we do not do here; on the contrary, we want to ``dig in'' to the proofs -- and hopefully enjoy it. The goal of this book is not to reach an encyclopedic completeness but to pursue the pleasure of completely understanding a complex proof with all of its clever insights. It is obvious that in such a pursuit complete treatment of the topics cannot possibly be guaranteed and that the selection of topics must necessarily be subjective. The selected topics come from the areas of computability, logic, (computational) complexity, circuit theory, and algorithms.

Where is the potential reader for this book to be found? I
believe he or she could be an active computer scientist or an
advanced student (perhaps specializing theoretical computer
science) who works through various topics as an independent study,
attempting to ``crack'' the exercises and by this means learns the
material on his or her own. I could also easily imagine portions of
this book being used as the basis of a seminar, as well as to
provide a simplified introduction into a potential topic for a *
Diplomarbeit* (perhaps even for a *Dissertation*).

A few words about the use of this book. A certain amount of
basic knowledge is assumed in theoretical computer science
(automata, languages, computability, complexity) and for some
topics probability and graph theory (similar to what my students
encounter prior to the *Vordiplom*). This is very briefly
recapitulated in the preliminary chapter. The amount of knowledge
assumed can vary greatly from topic to topic. The topics can be
read and worked through largely independently of each other, so one
can begin with any of the topics. Within a topic there are only
occasional references to other topics in the book; these are
clearly noted. References to the literature (mostly articles from
journals and conference proceedings) are made throughout the text
at the place where they are cited. The global bibliography includes
books which were useful for me in preparing this text and which can
be recommended for further study or greater depth. The numerous
exercises are to be understood as an integral part of the text, and
one should try to find one's own solution before looking up the
solutions in the back of the book. However, if one initially wants
to understand only the general outline of a result, one could skip
over the solutions altogether at the first reading. Exercises which
have a somewhat higher level of difficulty (but are certainly still
doable) have been marked with a diamond.

For proof-reading (the original German text) and for various suggestions for improvement I want to thank Gerhard Buntrock, Volker Claus, Uli Hertrampf, Johannes Köbler, Christoph Meinel, Rainer Schuler, Thomas Thierauf, and Jacobo Toran. Christoph Karg prepared a preliminary version of Chapter 14 as part of a course paper.

Uwe Schöning