Luís Antunes (Universidade do Porto, Portugal)

A crash course on computational complexity

Abstract: Computational Complexity had its origin in the mid 60s. It aims to investigate the intrinsic complexity of computational problems, and is based on the amount of resources (such as time and/or space and/or randomness and/or parallelism) necessary to solve a computational task (or class of tasks). During these three lectures we will briefly describe the motivation for the study of computational complexity and cover some historical marks. Then we will survey the major classical results and open problems. During the last lecture we will present the notion of Kolmogorov complexity and show that it can be an useful tool in computational complexity.