EBOOK An Introduction to Computational Complexity

e-ISBN: 978-83-233-8011-5

Michael Soltys is an associate professor in computer science at McMaster University in Ontario, Canada. He finished his Ph.D. in 2001 at the University of Toronto, under the supervision of Stephen Cook. He was a Visiting Ulam Professor in the Department of Mathematics at the University of Colorado at Boulder during the academic year 2007/2008. His research interests are computational complexity and logic. He is particularly interested in proof complexity, an area which investigates logical systems that use restricted reasoning based on concepts from computational complexity.
This book is a quick introduction, at a graduate level, to the field of computational complexity. It aims at presenting a collection of classical results in the field, rather than a comprehensive overview of complexity. It includes chapters on circuit complexity, proof complexity (a subfield of complexity that is rarely presented in similar textbooks) and randomized algorithms.
The material from which the book arises has been used as a graduate special topics course at McMaster University in Canada, the Jagiellonian University in Poland and the University of Colorado at Boulder in the U.S.A. The book provides a peek into powerful methods that have been used in attacks against the fundamental question of theoretical computer science, namely the famous P=NP question. It is the techniques themselves that have been emphasized by the Author, rather than the results obtainable by employing them. Thus, an important feature of the book is precisely that it affords a quick introduction to these techniques. For this reason the book might be of interest to anyone starting to work on problems in the fascinating field of computational complexity.
Preface 9
Notation 10
Acknowledgments 11
Chapter 1. Turing machines 13
1.1. Definition 13
1.2. Basic properties 15
1.3. Crossing sequences 16
1.4. Answers to selected exercises 20
1.5. Notes 22
Chapter 2. P and NP 23
2.1. Introduction  23
2.2. Reductions and completeness  25
2.3. Self-reducibility of satisfiability  28
2.4. Padding argument  30
2.5. Answers to selected exercises 32
2.6. Notes  33
Chapter 3. Space  35
3.1. Basic definitions and results  35
3.2. The inductive counting technique  38
3.3. Interactive Proof Systems  40
3.4. Answers to selected exercises  44
3.5. Notes  44
Chapter 4. Diagonalization and Relativization 45
4.1. Hierarchy theorems 45
4.2. Oracles and Relativization  49
4.3. Polynomial time hierarchy  53
4.4. More on Alternating TMs 56
4.5. Bennett’s Trick  57
4.6. Answers to selected exercises  58
4.7. Notes 59
Chapter 5. Circuits 61
5.1. Basic results and definitions  61
5.2. Shannon’s lower bound  65
5.3. The probabilistic method  67
5.4. Computation with advice 77
5.5. Answers to selected exercises . 78
5.6. Notes  78
Chapter 6. Proof Systems  81
6.1. Introduction  81
6.2. Resolution  83
6.3. A lower bound for  88
6.4. Automatizability and interpolation  91
6.5. Answers to selected exercises  96
6.6. Notes . 96
Chapter 7. Randomized Classes  97
7.1. Three examples of randomized algorithms 97
7.2. Basic Randomized Classes  102
7.3. The Chernoff Bound and Amplification  105
7.4. More on BPP 106
7.5. Toda’s theorem 109
7.6. Answers to selected exercises  112
7.7. Notes  114
Chapter 8. Appendix  115
8.1. NP-complete problems 115
8.2. A little number theory 118
8.3. RSA  121
8.4. The Isolation Lemma  123
8.5. Berkowitz's algorithm  124
8.6. Answers to selected exercises  132
8.7. Notes  133
Bibliography  135
Index  137