3 ECTS credits
75 h study time

Offer 1 with catalog number 4021173FNR for all students in the 1st semester at a (F) Master - specialised level.

1st semester
Enrollment based on exam contract
Grading method
Grading (scale from 0 to 20)
Can retake in second session
Taught in
Faculty of Sciences and Bioengineering Sciences
Computer Science
Educational team
Bart Bogaerts (course titular)
Activities and contact hours
18 contact hours Lecture
18 contact hours Seminar, Exercises or Practicals
Course Content

1. Computability theory

- Turing machines
- Church-Turing thesis
- Decidability
- Halting problem
- Reducibility
- Recursion theorem

2. Complexity theory

- Time complexity and the classes P and NP
- NP-completeness and the Cook-Levin theorem
- Other NP-complete problems

Additional info

Additional material:

1. Chapters 9 and 10 of Hopcroft, J.E., Motwani, R. and J.D. Ulmann, Introduction to Automata theory, Languages and Computation, 3rd edetion, Addison-Wesley, 2006.

2. Parts IV and V and the Appendices G–N of Rich, E. Automata, Computability and Complexity: Theory and Applications, Prentice-Hall, 2007.

3. Hofstadter, D.R. (1979) Godel, Escher, Bach: an Eternal Golden Braid, The Harvester Press, 1979.

Learning Outcomes

Algemene competenties

To introduce the basic concepts of the theory of computation and complexity theory and to show the relevance of this theory for a computer scientist.

• Knowledge and insight: After successful completion of the course the student should have insight into which problems and functions can in principle be solved or computed and which ones cannot. (S)he also will have insight in how efficiently computable problems can be computed and how to classify such problems into the different complexity classes.

• Use of knowledge and insight: The student should be able to solve computability and complexity problems (s)he encounters in practice.

• Judgement ability: The student should also be able to understand and apply the available techniques to shown that a problem is computable or not and when it is computable to which complexity class the problem belongs.

• Communication: The student should be able to communicate with experts when studying the computational and complexity aspects of problems.

• Skills: The student should be able to state formally a problem, to prove that statement and to show some creativity in finding that proof.


The final grade is composed based on the following categories:
Written Exam determines 100% of the final mark.

Within the Written Exam category, the following assignments need to be completed:

  • Written exam with a relative weight of 1 which comprises 100% of the final mark.

Additional info regarding evaluation

There is a written final exam. There are 2 theoretical questions marked on 6 points each and there are 2 exercises marked on 4 points each. These exercises are similar to but different from the exercises seen during the course.

Allowed unsatisfactory mark
The supplementary Teaching and Examination Regulations of your faculty stipulate whether an allowed unsatisfactory mark for this programme unit is permitted.

Academic context

This offer is part of the following study plans:
Master of Applied Sciences and Engineering: Computer Science: Artificial Intelligence
Master of Applied Sciences and Engineering: Computer Science: Multimedia
Master of Applied Sciences and Engineering: Computer Science: Software Languages and Software Engineering
Master of Applied Sciences and Engineering: Computer Science: Multimedia for Northwestern Polytechnical University (NPU)
Master of Applied Sciences and Engineering: Computer Science: Data Management and Analytics