Издательство Springer, 1998, -327 pp.
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 clack" the exercises and by this means leas 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 jouals 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.
Fundamental Definitions and Results.
The Priority Method.
Hilbert's Tenth Problem.
The Equivalence Problem fur LOOP(1)- and LOOP(2)-Programs.
The Second LBA Problem.
LOGSPACE, Random Walks on Graphs, and Universal Traversal Sequences.
Exponential Lower Bounds for the Length of Resolution Proofs.
Spectral Problems and Descriptive Complexity Theory.
Kolmogorov Complexity, the Universal Distribution, and Worst-Case vs. Average-Case.
Lower Bounds via Kolmogorov Complexity.
PAC-Leaing and Occam's Razor.
Lower Bounds for the Parity Function.
The Parity Function Again.
The Complexity of Craig Interpolants.
Equivalence Problems and Lower Bounds for Branching Programs.
The Berman-Hartmanis Conjecture and Sparse Sets.
Collapsing Hierarchies.
Probabilistic Algorithms, Probability Amplification, and the Recycling of Random Numbers.
The BP Operator and Graph Homorphism.
The BP-Operator and the Power of Counting Classes.
Interactive Proofs and Zero Knowledge.
P=PSPACE.
P?NP with Probability 1.
Superconcentrators and the Marriage Theorem.
The Pebble Game.
Average-Case Complexity.
Quantum Search Algorithms.
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 clack" the exercises and by this means leas 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 jouals 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.
Fundamental Definitions and Results.
The Priority Method.
Hilbert's Tenth Problem.
The Equivalence Problem fur LOOP(1)- and LOOP(2)-Programs.
The Second LBA Problem.
LOGSPACE, Random Walks on Graphs, and Universal Traversal Sequences.
Exponential Lower Bounds for the Length of Resolution Proofs.
Spectral Problems and Descriptive Complexity Theory.
Kolmogorov Complexity, the Universal Distribution, and Worst-Case vs. Average-Case.
Lower Bounds via Kolmogorov Complexity.
PAC-Leaing and Occam's Razor.
Lower Bounds for the Parity Function.
The Parity Function Again.
The Complexity of Craig Interpolants.
Equivalence Problems and Lower Bounds for Branching Programs.
The Berman-Hartmanis Conjecture and Sparse Sets.
Collapsing Hierarchies.
Probabilistic Algorithms, Probability Amplification, and the Recycling of Random Numbers.
The BP Operator and Graph Homorphism.
The BP-Operator and the Power of Counting Classes.
Interactive Proofs and Zero Knowledge.
P=PSPACE.
P?NP with Probability 1.
Superconcentrators and the Marriage Theorem.
The Pebble Game.
Average-Case Complexity.
Quantum Search Algorithms.