Text

Course syllabus - Computational complexity

Scope

7.5 credits

Course code

MAA513

Valid from

Autumn semester 2026

Education level

Second cycle

Progressive Specialisation

A1N (Second cycle, has only first-cycle course/s as entry requirements)

Main area(s)

Mathematics/Applied Mathematics

Organisation

Department of Business and Mathematics

Ratified

2019-12-09

Revised

2025-11-03

Literature lists

Course literature is preliminary up to 8 weeks before course start. Course literature can be valid over several semesters.

    • Ratified date: 2021-02-01
    • Latest update: 2025-05-27

    Books

    Moore, Cristopher; Mertens, Stephan

    The nature of computation

    ISBN: 9780199233212

    LIBRIS-ID: 11354166

    Oxford, Oxford University Press, 985 s.

Objectives

The objective of the course is to give the student the opportunity to acquire basic knowledge of the theory of computational complexity and its applications.

Learning outcomes

Upon completion of the course, the student is expected to be able to

  1. define the complexity classes P, NP, PSPACE, BPP and BPQ, and explain how they are related
  2. explain some central NP-hard problems, such as the traveling salesperson problem and 3-SAT, and some problems in P
  3. carry out simple proofs by reduction to show that a problem is NP-hard
  4. describe approximation algorithms for certain NP-hard problems
  5. explain expected areas of use, and limitations of, quantum computers

Course content

  • Turing machines, formal languages, boolean circuits
  • Big-O notation
  • Complexity classes: P, NP, PSPACE, BPP, BQP
  • Approximation algorithms and approximability
  • Quantum algorithms, limitations of quantum computing
  • Applications within optimization, machine learning, data analysis, and mathematical proof

Specific requirements

Discrete Mathematics, 7.5 credits, Probability, 7.5 credits and Programming, 7.5 credits, or equivalent. In addition, Swedish course 3 or Swedish level 3 and English course 6 or English level 2 are required. For courses given entirely in English exemption is made from the requirement in Swedish course 3 or Swedish level 3.

Examination

TEN1, Written examination, 7.5 credits, individual written examination concerning learning outcomes 1-5, grades Fail (U), 3, 4 or 5.

A student who has a certificate from MDU regarding disability study support, can request adaptions for the examination. It is the examiner who takes decisions on any adaptions, based on the certificate and other conditions.

Grade

Grading scale: 5, 4, 3