Introduction to Complexity Theory

Undergraduate / Graduate

Computability: Turing machines, Universal Turing machines and the Church-Turing thesis. Undecidability. Reducibilities. Complexity--the study of the amount of resources -- time, space, communication, randomness, etc -- needed in computations: Time and space complexity classes, nondeterministic and probabilistic computations. Complete problems. Lower bounds, and the big open problems: P vs NP, space vs. time, etc. Communication Complexity.