Lecture Notes

 

 

0

Turing Machine Models

1

Basic Complexity Classed

2

P-NP-coNP

3

Space Complexity

4

Diagonalization

5

Circuit Complexity (incomplete)

6

Polynomial Hierarchy

7

Randomized Computation

8

Recursive and Lambda Definable Functions

Started, but could not complete.

Read

Complexity Theory’s 50-Year Journey to the Limits of Knowledge

         Previous Page