MM850: Complexity and Computability

Study Board for Natural Sciences

Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N310053102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Master

STADS ID (UVA): N310053101
ECTS value: 10

Date of Approval: 22-10-2025


Duration: 1 semester

Version: Approved - active

Internal Course Code

MM850

Comment

The course is co-read with: DM553: Complexity and Computability (10 ECTS).
The course is elective for students in Mathematics, Applied Mathematics, and Mathematics-Economics.

Entry requirements

The course cannot be chosen by students who have passed DM553

Academic preconditions

Students taking the course are expected to:

  • Have knowledge of basic algorithms for manipulating (representations of) sets of numbers and graphs, along with analysis of algorithms.
  • Be able to use basic mathematical argumentation, including proof by induction, proof by contradiction and logic expressions
  • Be familiar with the use of combinatorial techniques to develop algorithms.

The course builds on the knowledge acquired in the course MM541 Combinatorial mathematics.

Course introduction

The aim of the course is to enable the student to 
  • Apply formalisms of formal languages in order to formulate decision problems precisely
  • Work with finite automata, regular expressions and context-free grammars.
  • Judge whether a given problem may be solved by a computer or is undecidable.
  • Argue that problems are NP-complete. 
  • Judge the possibility to develop an approximation or fixed parameter algorithm for a given NP-hard optimization problem.
These competencies are important both when one wishes to develop new algorithms for a given problem and when one wants to judge whether a given problem may be possible to solve efficiently (possibly only approximately) by a computer.

The course forms the basis for taking elective candidate level courses containing one or more of the following elements: complexity of algorithms, approximation algorithms and computability.
Together with courses of the type described above, this course also provides a basis for doing a masters thesis on algorithmic and complexity theoretic subjects.

Expected learning outcome

The learning objectives of the course is that the student demonstrates the ability to:
  • Judge the complexity of decision problems.
  • Judge the computational power of various models of computation.
  • Construct finite automata, regular expressions, or context-free grammars for simple languages.
  • Prove that a given language, which in nature resembles those from the course, cannot be recognized by a finite automaton or a Turing machine.
  • Design new approximation algorithms for a given problem which in nature resembles those from the course.
  • Prove that a given decision problem which in nature resembles those from the course is NP-complete or undecidable.
  • Give clear, precise definitions and proofs for the above.

Content

The following main topics are contained in the course:
  • Regular languages and context-free languages
  • Turing machines
  • Decidability
  • Problem reductions
  • The complexity classes P and NP
  • The theory of NP-completeness
  • Approximation algorithms
  • Exact Algorithms

Literature

See itslearning  for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

June

Tests

Oral exam

EKA

N310053102

Assessment

Second examiner: External

Grading

7-point grading scale

Identification

Full name and SDU username

Language

Normally, the same as teaching language

Duration

Oral exam: 25 minutes per student and no preparation.

Examination aids

Assignments during the semester: All common aids are allowed.

Oral exam: No aids allowed.

ECTS value

10

Additional information

The exam consists of an oral exam and a number of assignments handed in during the course. The final grade is given on the basis of an overall assessment of assignments and the oral exam. The external examiner will be able to see the assignments. 

The re-exam is an oral exam. External examiner, Danish 7 mark scale. 

Indicative number of lessons

72 hours per semester

Teaching Method

Planned lessons:
Total number of planned lessons: 72
Hereof:
Common lessons in classroom/auditorium: 36
Team lessons in classroom: 36

The common lessons consist of classical lecturing, intertwined with discussion and questions (from the teacher to the students as well as the other way around). In the team lessons, solutions to exercises will be discussed. The students should attempt to solve the exercises before coming to class.

Other planned teaching activities: 
  • Self-study of the teaching material
  • Solving weekly assignments in order to discuss these at the tutorials
  • Written assignments as part of the exam
  • Self-guided follow-up on the common lessons
  • Review for the exam

Teacher responsible

Name E-mail Department
Lene Monrad Favrholdt lenem@imada.sdu.dk Institut for Matematik og Datalogi

Timetable

Administrative Unit

Institut for Matematik og Datalogi (matematik)

Team at Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period

Transition rules

Transitional arrangements describe how a course replaces another course when changes are made to the course of study. 
If a transitional arrangement has been made for a course, it will be stated in the list. 
See transitional arrangements for all courses at the Faculty of Science.