Computational Complexity, 7.5 Credits

Contents

Having completed the course Efficient Algorithms, the student is already aware of the fact that 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.

Part 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.

Part 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.

Expected learning outcomes

Knowledge and understanding
Upon completion of the course, the student will, with mathematical accuracy, be able to define, explain and discuss

• Upon completion of the course the student shall, with mathematical accuracy, be able to define, explain and discuss
  the concept of computational complexity with respect to execution time and memory space, and connections between them (FSR 1)
• the most central complexity classes and how they are related (FSR 2)
• the main open issues regarding the relationships between these complexity classes (FSR 3)
• recurring methods used to prove the relationship between complexity classes, in particular "achievability method" or specific problems, especially reductions between problems (FSR 4).

Skills and Abilities
Upon completion of the course, the student should be able to

• independently read a formal mathematical text (the textbook), present it to others, and discuss both the acquired knowledge and possible difficulties (FSR 5)
• with mathematical accuracy reason about the meaning, formalization and use of the terms computational problem, computational complexity, and completeness, and the relationships between them (FSR 6)
• based on given examples, create reductions between problems, formulate them in writing, and utilize them to prove that a problem is complete for a given complexity class (FSR 7).

Values ​​and approaches
Upon completion of the course, the student should be able to

• critically and in a knowledge-based manner orally discuss the practical significance and limitations of the theoretical results with peers (FSR 8).

Required Knowledge

Univ: To be admitted you must have (or equivalent) 90 ECTS-credits including 60 ECTS-credits in Computing Science or at least two years of completed studies within a study programme (120 ECTS-credits). In both cases, the studies must include at least 7.5 ECTS-credits within Efficient algorihtms. 

Proficiency in English equivalent to Swedish upper Secondary course English A/5. Where the language of instruction is Swedish, applicants must prove proficiency in Swedish to the level required for basic eligibility for higher studies.

Form of instruction

The teaching is as described in section Contents and consists of both overview lectures and student-led presentations and discussions of the material.
 

Examination modes

Part 1 (FSR 1-4, 6-8) is examined by a written exam. The grades given on this part are Fail (U), Pass (3) or Pass with Merit (4), and Pass with Distinction (5). For all students who do not pass the regular examination there are other opportunities to do the examination.

Part 2 (FSR 1-8) is examined by the student's submitted summaries and presentations. In Part 2, one of the grades Fail (U) and Pass (G) is given. For grade G it is necessary that all but a maximum of 3 summaries be submitted in time and be assessed as completed, and that all presentations given by the student will be assessed as completed. The number of summaries vary depending on their content. Usually 12 summaries are written but never more than 14.

In order for a summary or presentation to be assessed as completed, it should clearly show that the student has made an effort to penetrate the content and with some success reflected on it as well as on their own level of understanding. Thus, it is not a demand that the student has already managed to obtain a fully correct understanding of the entire content discussed. However, it should be clear that the material has been treated and reflected on at an appropriate level for an advanced course.

A student who receives the grade U on Part 2 will be given the opportunity to be re-examined on this part at a later date after the end of the course. This is done by carefully processing all the part-assignments that received the grade "not complete" and submitting a written statement for these. In this case, higher demands are placed on the completeness and correctness than at the regular examination. This is to compensate the fact that the student has not participated in the discussion regarding this topic. If a student has been inactive on the whole of part 2 during the course, they may not participate in this re-examination but must instead participate in the examination at the next course offering. This is because the student has missed all oral discussions during the course and therefore does not fulfill FSR 8. Oral discussions can not be replaced by written reports.

In order to pass the examination of the course as a whole, the minimum grade is required on both parts. On the course in its entirety, one of the grades Fail (U), Pass (3) or Pass with Merit (4), and Pass with Distinction (5) is given. The final grade of the course is a summary assessment of the results on the course and is decided upon when both mandatory parts are passed. The overall grade usually follows the grade on Part 1. However, if the result on Part 1 is just below the requirement for a higher grade, a particularly good achievement on Part 2 may motivate raising the grade.

A student who has taken two tests for a course or segment of a course, without passing, has the right to have another examiner appointed, unless there exist special reasons (Higher Education Ordinance Chapter 6, section 22). Requests for new examiners are made to the head of the Department of Computing Science.

A student who has passed an examination may not be re-examined.

Examination based on this syllabus is guaranteed for two years after the first registration on the course. This applies even if the course is closed down and this syllabus ceased to be valid.

TRANSFER OF CREDITS
Students have the right to be tried on prior education or equivalent knowledge and skills acquired in the profession can be
credited for the same education at Umeå University. Application for credit is submitted to the Student Services / Degree.
For more information on credit transfer available at Umeå University's student web, www.student.umu.se, and the Higher
Education Ordinance (Chapter 6). A refusal of crediting can be appealed (Higher Education chapter 12) to the University
Appeals Board. This applies to the whole as part of the application for credit transfer is rejected.

Other regulations

This course may not be used towards a degree, in whole or in part, togehter with another course of similar content. If in
doubt, consult the student counselors at the Department of Computing Science and / or the program director of your
program.