Download Notes on Computational Complexity Theory, This note provides an introduction to the theory of computational complexity. Topics lined includes: Models of computation, Time and space complexity classes, Nonterminism and NP, diagonalization, Oracles and relativization, Alternation, space complexity, Natural proofs, randomized classes, counting classes, Descriptive complexity and Interactive proofs.


1 Introduction

2 Problems and languages

3 Models of computation

4 Time and space complexity classes

5 Nonterminism and NP

6 Diagonalization

7 Oracles and relativization

8 Alternation

9 Space complexity

10 Circuit complexity

11 Natural proofs

12 Randomized classes

13 Counting classes

14 Descriptive complexity

15 Interactive proofs

16 Probabilistically-checkable proofs and hardness of approximation