Uusi opinto-opas (sisältäen myös opetusohjelmat) lukuvuodelle 2018-2019 sijaitsee osoitteessa https://opas.peppi.utu.fi . Tältä sivustolta löytyvät enää vanhat opinto-oppaat ja opetusohjelmat.

The new study guide (incl. teaching schedules) for academic year 2018-2019 can be found at https://studyguide.utu.fi. This site contains only previous years' guides.

x !
Arkistoitu opetussuunnitelma 2016–2018
Selaamasi opetussuunnitelma ei ole enää voimassa. Tarkista tiedot voimassa olevasta opetussuunnitelmasta.
MATE5290 Algorithmic complexity 10 op
Organised by
Person in charge
Department of Mathematics and Statistics, Juhani Karhumäki
Preceding studies
Basics on algorithms, in particular algorithmic thinking. Automata theory course is recommended.

Learning outcomes

to understand basic concepts and methods in algebraic complexity; to be able to reduce problems to each other, both decidable and undecidable ones


The complexity theory of algorithms has been developed over the past 40 years or so. It culminates the celebrated P=NP problem. This problem asks whether many natural algorithmic problems, like the factorization of composite numbers, can be solved by a polynomial time algorithm. In the course basic properties of complexity classes are presented. In particular, the existence of so-called NP-complete problems are shown, and natural examples of those are given. Also undecidable problems are considered and classified.

Teaching methods

Teaching method Contact Online
Lectures 56 h 0 h
Exercises 28 h 0 h

Not lectured 2014-2016.

Teaching language


Modes of study

Option 1
Available for:
  • Degree Programme Students
  • Other Students
  • Doctoral Students
  • Exchange Students
  • In English
Written exam
  • In English
Option 2
Available for:
  • Degree Programme Students
  • Other Students
  • Doctoral Students
  • Exchange Students
Written exam
  • In English


Numeric 0-5.

Study materials

Lecture notes; Papadimitriou: Computational Complexity, Addison-Wesley, 1994.

Belongs to following study modules

Matematiikan ja tilastotieteen laitos
Tulevaisuuden teknologioiden laitos
Archived Teaching Schedule. Please refer to current Teaching Shedule.
Implementation details are unavailable.
Matematiikan ja tilastotieteen laitos
MDP in Information Security and Cryptography