Strings, sets, languages and functions. Notation and terminolgy.
Computability. Diagonalization. Examples of uncomputable problems.
Reductions among problems.
Introduction to complexity. Complexity classes.
Polynomial time complexity. Deterministic and nondeterministic computation. The classes P and NP. NP-completeness. Examples of NP-complete problems.
Other complexity classes. The class PSPACE and PSPACE-completeness.
Applications of complexity results. Cryptography. Interactive and zero-knowledge proofs.