Home

Education

Postgraduate course

Complexity Theory

  • ECTS credits10
  • Teaching semesterSpring
  • Course codeINF235
  • Number of semesters1
  • Language¬†English
  • Resources

Semester of Instruction

Spring

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.

Learning Outcomes

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

INF234

Compulsory Assignments and Attendance

Exercises.

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.

Grading Scale

The grading scale used is A to F. Grade A is the highest passing grade in the grading scale, grade F is a fail.

Subject Overlap

I235: 10 ECTS

Contact

Contact Information

studieveileder@ii.uib.no

Exam information

  • Type of assessment: Written examination

    Withdrawal deadline
    01.11.2017