| Introduction | p. 1 |
| Issues in Computational Complexity | p. 1 |
| The Power of Randomness | p. 1 |
| The Power of Guessing | p. 5 |
| The Power of Memory | p. 6 |
| Contributions in This Dissertation | p. 8 |
| Simulations | p. 8 |
| Separations | p. 9 |
| Preliminaries | p. 13 |
| Computational Problems | p. 13 |
| Models of Computation, Resource Bounds, and Complexity Classes | p. 18 |
| Turing Machines | p. 19 |
| Uniform Families of Boolean Circuits | p. 21 |
| Nondeterministic Turing Machines | p. 24 |
| Alternating Turing Machines | p. 27 |
| Randomness | p. 31 |
| Randomized Computations | p. 32 |
| Randomized Proof Checking | p. 35 |
| Pseudo-Random Generators | p. 37 |
| Reductions and Completeness | p. 42 |
| Relativization | p. 42 |
| Reductions | p. 44 |
| Complete Problems | p. 46 |
| Resource-Bounded Measure | p. 47 |
| Motivation | p. 47 |
| Martingales | p. 48 |
| Properties | p. 50 |
| Derandomizing Arthur-Merlin Games | p. 53 |
| Introduction | p. 53 |
| Notation | p. 56 |
| Derandomizing Arthur-Merlin Games | p. 57 |
| Proof of Lemma 3.3.1 | p. 60 |
| Proof of Theorem 3.3.1 | p. 61 |
| Proof of Theorem 3.3.2 | p. 63 |
| A General Framework for Derandomization | p. 64 |
| More Applications | p. 66 |
| Valiant-Vazirani | p. 66 |
| Learning Circuits | p. 69 |
| Rigid Matrices | p. 70 |
| Universal Traversal Sequences | p. 72 |
| Conclusion and Open Questions | p. 76 |
| Sparseness of Complete Languages | p. 77 |
| Introduction | p. 77 |
| The Sparse Hard Language Problem for NP | p. 77 |
| The Sparse Hard Language Problem for P | p. 78 |
| Overview of this Chapter | p. 79 |
| Deterministic Reductions | p. 81 |
| Previous Work | p. 81 |
| Main Result | p. 85 |
| Generic Theorem for P | p. 92 |
| Extension to Classes Other Than P | p. 95 |
| Randomized Reductions | p. 98 |
| Previous Work | p. 98 |
| Main Result | p. 99 |
| Randomized Generic Theorem for P | p. 106 |
| Extension to Classes Other Than P | p. 109 |
| Conclusion and Open Questions | p. 112 |
| Autoreducibility of Complete Languages | p. 113 |
| Introduction | p. 113 |
| Definitions | p. 115 |
| Nonautoreducibility Results | p. 115 |
| Adaptive Autoreductions | p. 116 |
| Nonadaptive Autoreductions | p. 121 |
| Autoreducibility Results | p. 122 |
| Adaptive Autoreductions | p. 123 |
| Nonadaptive Autoreductions | p. 130 |
| Randomized and Nonuniform Autoreductions | p. 134 |
| Separation Results | p. 137 |
| Conclusion and Open Questions | p. 139 |
| The Size of Randomized Polynomial Time | p. 141 |
| Introduction | p. 141 |
| The Zero-One Law for BPP | p. 142 |
| Generalization | p. 143 |
| Conclusion and Open Questions | p. 144 |
| The Frequency of Complete Languages | p. 145 |
| Introduction | p. 145 |
| Complete Languages under Nonadaptive Reductions with n¿ Queries and a Small Span Theorem | p. 146 |
| Complete Languages for EXP under Adaptive Reductions with nc Queries | p. 152 |
| Complete Languages for EXP under Nonadaptive Reductions | p. 154 |
| Conclusion and Open Questions | p. 159 |
| The Frequency of Autoreducible Languages | p. 161 |
| Introduction | p. 161 |
| Betting Games | p. 163 |
| From Betting Games to Martingales | p. 165 |
| Sampling Results | p. 168 |
| Autoreducible Languages | p. 172 |
| Adaptively Autoreducible Languages | p. 172 |
| Nonadaptively Autoreducible Languages | p. 174 |
| Covering Autoreducible Languages by Martingales | p. 175 |
| Conclusion and Open Questions | p. 181 |
| References | p. 183 |
| Notation Index | p. 191 |
| Subject Index | p. 195 |
| Table of Contents provided by Publisher. All Rights Reserved. |
