Bachelor 2024/2025

Theory of Computation

Type: Compulsory course (Applied Mathematics and Information Science)

Area of studies: Applied Mathematics and Information Science

Delivered by: Big Data and Information Retrieval School

Where: Faculty of Computer Science

When: 3 year, 1, 2 module

Mode of studies: offline

Open to: students of one campus

Language: English

ECTS credits: 5

Contact hours: 56

Course Syllabus

Abstract

The aim of computational complexity is to classify computational problems by their difficulty. Here, difficulty, is measured by various resources needed to provide answers, such as computation time, space, randomness, circuits sizes. In particular, we train to distinguish polynomial time solvable problems and NP-hard problems. The latter are believed to require exponential time for worst case instances, and hence, in applications, one needs to restate the problem, use heuristics, or optimize exhaustive searches. The latter, is studied theoretically in the field of parameterized complexity