Theory of Computation

2024/2025

Учебный год

ENG

Обучение ведется на английском языке

5

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс обязательный

Когда читается:

3-й курс, 1, 2 модуль

Преподаватели

Баувенс Бруно Фредерик Л.

Иванашев Ярослав Маратович

Лукьяненко Никита Сергеевич

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

Learning Objectives

• Know the parameterized complexity classes FPT, W[i], XP. Apply kernelization technique to obtain FPT-algorithms
• Know famous streaming algorithms, such as SpaceSaving, CountMinSketch to find the most frequent element
• Oracle computation and understand the diagonalization barrier in solving the P vs NP problem
• Prove that PSPACE = NPSPACE and that the TQBF problem is PSPACE complete
• Know the proof of the Cook-Levin theorem: 3SAT is NP-complete

Expected Learning Outcomes

• Definitions of Turing machines. Classes TIME(f(n)) and SPACE(f(n)). Time and space hierarchy theorems
• Definitions of the classes L, NL, P, NP, PSPACE, EXP, NEXP, EXPSPACE, BPP, RP, #P, and inclusions between them. Know some famous problems in these classes
• In particular, distinguishing between problems in P, that are NP-complete, and that are PSPACE-complete

Course Contents

• This course: what and why?
• Turing machines
• Hierarchy theorems
• The class NP
• NP-completeness
• Circuits
• Complexity zoo
• PSPACE
• Probabilistic computation
• Streaming algorithms
• Parameterized complexity
• Approximation algorithms

Assessment Elements

• Homework
  Every seminar list contains 2 homework questions similar as the questions in the seminar. Every 14 days, 4 questions need to be submitted. Sometimes the HW contains bonus marks, they are added to the score of the exam.
• Colloquium
  In December. The student receives 2 questions from a list of questions, given 2 weeks in advance. Answers are prepared in writing and the teacher checks understanding of the answers by asking for details or to work out simple examples. Students may not consult anything
• Exam
  During session in December. A written examination is held past Module 1. Students may use the major textbooks and the lecture notes given in the wiki. The exam happens in a computer room. There are 4 questions similar to the one of the seminars and the homework. The marks

Interim Assessment

• 2024/2025 2nd module
  0.35 * Colloquium + 0.3 * Exam + 0.35 * Homework

Bibliography

Recommended Core Bibliography

• Introduction to the theory of computation, Sipser, M., 2013

Recommended Additional Bibliography

• The nature of computation, Moore, C., 2012

Authors

• OBEDKOV SERGEY ALEKSANDROVICH
• BAUVENS Bruno Frederik L
• PODOLSKIY VLADIMIR VLADIMIROVICH