Skip to content
Main menu hidden.

Computational Complexity

  • Number of credits 7.5 credits
  • Level Master’s level
  • Starting Autumn Term 2024

About the course

Some algorithms solve a computational problem more efficiently than others. An important aspect of working as a computer scientist is to find efficient ways to solve a given problem. Sometimes one is successful, sometimes not. But how do we know in the latter case whether this is due to our own inability or lies in the nature of the problem, i.e. whether the problem can be solved effectively at all? Each problem has an inherent computational complexity that determines if it is solvable and, if so, how efficiently it can be solved. This leads to a categorization of problems in different classes with regard to their inherent complexity. Understanding this is important because it shows which level of efficiency one can reasonably expect. On the one hand, this leads to more efficient algorithms to the extent possible. On the other hand, it prevents the computer scientist from wasting energy by trying to achieve the impossible.

The course addresses and formalises this inherent complexity of computational problems, resulting in the categorization of problems into different complexity classes, known and unknown relationships between these classes, and the concept of complete problems. The following aspects are addressed: Formalization of computational complexity (primarily in terms of time and memory space) and its practical significance, the speedup theorem and the extended Church-Turing thesis, deterministic and non deterministic complexity classes (predominantly (N)TIME(f(n)), (N)SPACE(f(n)), P, NP, (N)EXPTIME, L, NL, PSPACE; complement classes to those) and what is known or unknown about their mutual relationship, reducing a problem to another one, completeness.

Application and eligibility

Computational Complexity, 7.5 credits

Visa tillfällen för föregående termin Autumn Term 2024 Det finns inga senare terminer för kursen


1 November 2024


19 January 2025

Study location




Type of studies

Daytime, 50%

Required Knowledge

At least 90 ECTS, including 60 ECTS Computing Science. At least 7.5 ECTS discrete mathematics; 7.5 ECTS data structures and algorithms; and 7.5 ECTS formal languages. Proficiency in English equivalent to the level required for basic eligibility for higher studies.

Entry requirements


Academic credits Applicants in some programs at Umeå University have guaranteed admission to this course. The number of places for a single course may therefore be limited.

Application code



Application deadline was 15 April 2024. Please note: This second application round is intended only for EU/EEA/Swiss citizens. Submit a late application at Universityadmissions.se.

Application and tuition fees

As a citizen of a country outside the European Union (EU), the European Economic Area (EEA) or Switzerland, you are required to pay application and tuition fees for studies at Umeå University.

Application fee

SEK 900

Tuition fee, first instalment

SEK 17,850

Total fee

SEK 17,850

Contact us

Please be aware that the University is a public authority and that what you write here can be included in an official document. Therefore, be careful if you are writing about sensitive or personal matters in this contact form. If you have such an enquiry, please call us instead. All data will be treated in accordance with the General Data Protection Regulation.

Course is given by
Department of Computing Science