Introduction to complexity theory, lecture notes

Table of Contents......Page 16 Lecture 1 - The P vs NP Question......Page 23 Lecture 2 - NP-completeness and Self Reducibility......Page 31 Lecture 3 - More on NP and some on DTIME......Page 45 Lecture 4 - Space Complexity......Page 57 Lecture 5 - Non-Deterministic Space......Page 65 Lecture 6 - Inside Non-Deterministic Logarithmic Space......Page 79 Lecture 7 - Randomized Computations......Page 95 Lecture 8 - Non-Uniform Polynomial Time......Page 113 Lecture 9 - The Polynomial Hierarchy (PH)......Page 123 Lecture 10 - The Counting Class #P......Page 137 Lecture 11 - Interactive Proof Systems......Page 157 Lecture 12 - Probabilistically Checkable Proof Systems......Page 171 Lecture 13 - Pseudorandom Generators......Page 187 Lecture 14 - Pseudorandomness and Computational Difficulty......Page 211 Lecture 15 - Derandomization of BPP......Page 221 Lecture 16 - Derandomizing Space-Bounded Computations......Page 235 Lecture 17 - Zero-Knowledge Proof Systems......Page 247 Lecture 18 - NP in PCP[poly, O(1)]......Page 269 Lecture 19 - DTIME vs DSPACE......Page 285 Lecture 20 - Circuit Depth and Space Complexity......Page 293 Lecture 21 - Communication Complexity......Page 305 Lecture 22 - Monotone Circuit Depth and Communication Complexity......Page 315 Lecture 23 - The FORK Game......Page 329 Lecture 24 - Average Case Complexity......Page 337 Lecture 25 - Computational Learning Theary......Page 349 Lecture 26 - Relativization......Page 365