Computational Complexity 7.5 credits

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.

Module 1, Concepts, results and proofs, 3 ECTS credits, consists of lectures that introduce and discuss concepts, results and their proofs according to the above contents desciption. Every lecture is related to one ore more sections of the textbook and provides an introduction to the material without considering any details. The goal is to make it easier for the student to obtain a deeper understanding by working with the material themselves.

Module 2, Deepening, reflection, and discussion, 4.5 ECTS credits, consists of the student's own work with the textbook, and student-guided discussion sessions. When the teacher has presented an overview of sections in the textbook, the student reads those sections and prepares a basic presentation of the material as a basis for discussion with the classmates. A mandatory summary of the central points is handed in before the next lecture (about 1 page). The summary shall in particular mention aspects the student did not manage to comprehend or feels uncertain about. The same holds for possible exercises that the teacher may specify to provide guidance. Students will then be selected in random order to present the material based on their own understanding, and to lead the discussion in the class. Every student has to make at least one such presentation.

Show syllabus

Apply

Autumn 2025
- Computational Complexity
  
  Second admissions round for EU/EEA citizens
  
  Autumn 2025 / Umeå / English / On site
  
  Submit a late application
  
  Show more Show less
  
  Starts
  3 November 2025
  
  Ends
  18 January 2026
  
  Number of credits
  7.5 credits
  
  Type of studies
  On site
  
  Study pace
  50%
  
  Teaching hours
  Daytime
  
  Study location
  Umeå
  
  Language
  English
  
  Application code
  UMU-57234
  
  Eligibility 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.
  
  Selection
  Academic credits
  
  Application
  Application deadline was 15 April 2025. 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 19,038
  
  Total fee: SEK 19,038
  
  Details about tuition, fees and funding

Apply online via universityadmissions.se
You apply to our programmes and courses via universityadmissions.se – the official website for higher education applications in Sweden. There, you can track your application, check that your documents have been registered, and log in to find our your admission results.
 
Late applications
Admissions to most programmes and courses typically close after the final application deadline. However, some programmes and courses may still accept late applications if seats are available. These are marked “Open for late application” on universityadmissions.se. Please note that late applications are not guaranteed to be reviewed.

More about application and admission

Explore your future at Umeå University

Join a vibrant academic community where high-quality education meets groundbreaking research in science, technology, humanities, and the arts. At Umeå University, you will learn from passionate, expert teachers and benefit from a close connection between research, education, collaboration, and innovation.

World's most satisfied international students

#1 globally in the main categories of Living, Support, and Overall Satisfaction.
A university with health at its core

Umeå University is certified as a Healthy Campus, with many initiatives that promote health and well-being.

Questions about the course?

Subject

Describe your enquiry or ask a question

First name

Last name

Email address

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.