Introduction to Theory of Computation and Computational Complexity
About the course:
This course introduces the fundamentals of the theory of computation and complexity theory. An underlying theme is the use of logic to understand computation and complexity.
Topics covered include: turing machines, undecidability, first-order logic, second-order logic, Godel's theorems, complexity theory, and logical characterizations of P and NP.
Lecture Notes: