Semester of Instruction
Objectives and Content
In Computational Complexity Theory we consider what happens when we limit the resources (time or space) available to solve a problem algorithmically. This limit is expressed as a function of the input size, and for various such functions we consider the class of problems that can be solved within the specific resource bound. The most well-known classes are called P and NP, denoting the problems solvable in polynomial-time, and those solvable in non-deterministic polynomial time. We will encounter many more such complexity classes. The course gives a precise formal definition of the algorithm concept via Turing machines. The main emphasis is on the relationships between the various classes, and techniques for showing completeness, i.e. that a problem is among the hardest for a particular class, in a well-defined sense.
At the completion of INF235 the student should:
- have a deeper understanding of what an algorithm is and of which problems that theoretically can be solved by an algorithm.
- understand the relationship between formal languages and Turing machines.
- know how to classify problems into complexity classes for time and memory usage.
- be able to decide which problems can be feasibly solved, either using an exact or an approximate method.
Required Previous Knowledge
At least 60 ECTS in computer science, preferably including some mathematics
Recommended Previous Knowledge
Compulsory Assignments and Attendance
Compulsory assignments are valid two semesters, the semester of the approval and the following semester.
Forms of Assessment
Written exam. It is opportunity for grades on exercises, which can be included in the final grade. If less than 20 students are taking the course, it can be oral exam.
No aids allowed.
The grading scale used is A to F. Grade A is the highest passing grade in the grading scale, grade F is a fail.
I235: 10 ECTS
Type of assessment: Written examination
- Withdrawal deadline