Text

Course syllabus - Computational complexity

Scope

7.5 credits

Course code

MAA513

Valid from

Autumn semester 2020

Education level

Second cycle

Progressive Specialisation

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

Main area(s)

Mathematics/Applied Mathematics

School

School of Education, Culture and Communication

Ratified

2019-12-09

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: 2021-02-01

    Books

    Moore, Cristopher; Mertens, Stephan

    The nature of computation

    Oxford : Oxford University Press, 2011 - 985 s.

    ISBN: 9780199233212 LIBRIS-ID: 11354166

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 B/Swedish 3 and English A/English 6 are required. In cases when the course is offered in English, the requirement for Swedish B/Swedish 3 is excluded.

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 a disability has the opportunity to submit a request for supportive measures during written examinations or other forms of examination, in accordance with the Rules and Regulations for Examinations at First-cycle and Second-cycle Level at Mälardalen University (2020/1655). It is the examiner who takes decisions on any supportive measures, based on what kind of certificate is issued, and in that case which measures are to be applied.

Suspicions of attempting to deceive in examinations (cheating) are reported to the Vice-Chancellor, in accordance with the Higher Education Ordinance, and are examined by the University’s Disciplinary Board. If the Disciplinary Board considers the student to be guilty of a disciplinary offence, the Board will take a decision on disciplinary action, which will be a warning or suspension.

Study guide

Grade

Grading scale: 5, 4, 3