Gems of Theoretical Computer Science

by U. Schöning and R. Pruim

• 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.

Table of Contents

Preface to the English Edition

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.

Preface to Original German Edition

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.