We use cookies to ensure you have the best browsing experience on our website and to help us improve the site. By continuing to browse the site you are agreeing to our use of cookies. Read more about how we use cookies here

This page in Swedish

Computational Complexity Theory, 3 credits

Course information

Research Education Subject

  • Computer Science

Course Syllabus

Course Syllabus


Course content

This course examines the basic principles of complexity theory. It refreshes the basics of algorithm analysis (the analysis of resource usage of given algorithms) and of the principal formal properties of algorithms (correctness, completeness, optimality). Specifically, it gives an overview of the principal notations and methods for characterizing non-recursive and recursive algorithms. The course also provides an overview of the main issues problem complexity, that is, the study of the cost of solving interesting problems, given a suitable model of computation. Within this topic, we overview the principal models of computation used to characterize problem complexity (e.g., Turing Machines), their equivalence to computable functions (Church-Turing Thesis), and the principal problem complexity classes (NL, LOG, P, NP, PSPACE, EXPTIME, EXPSPACE).