Introduction to complexity theory, lecture notes

Goldreich O.

Table of contents :
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