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:

Introduction

Turing Machines

Undecidability

Logic

First-Order Logic

Second-Order Logic

Complexity Classes

Reductions

NP-Completeness