Gems of Theoretical Computer Science

by U. Schöning and R. Pruim

This page contains of the book Gems of Theoretical Computer Science by U. Schöning and R. Pruim, published in 1998 by Springer Verlag.

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

Table of Contents

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

Preface to the English Edition

While I was visiting Boston University during the 1996--97 academic year, I noticed a small book, written in German, on a shelf in Steve Homer's office. Curious, I borrowed it for my train ride home and began reading one of the chapters. I liked the style and format of the book so much that over the course of the next few months I frequently found myself reaching for it and working through one chapter or another. This was my introduction to Perlen der Theoretischen Informatik.

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 Pruim
July, 1998

Preface to Original German Edition

In the summer semester of 1993 at Universität Ulm, I tried out a new type of course, which I called Theory lab, as part of the computer science major program. As in an experimental laboratory -- with written preparatory materials (including exercises), as well as materials for the actual meeting, in which an isolated research result is represented with its complete proof and all of its facets and false leads -- the students were supposed to prove portions of the results themselves, or at least to attempt their own solutions. The goal was that the students understand and sense ``how theoretical research is done.'' To this end I assembled a number of outstanding results (``highlights,'' ``pearls,'' ``gems'') from theoretical computer science and related fields, in particular those for which some surprising or creative new method of proof was employed. Furthermore, I chose several topics which don't represent a solution to an open problem, but which seem in themselves to be surprising or unexpected, or place a well-known problem in a new, unusual context.

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