• A
• A
• A
• ABC
• ABC
• ABC
• А
• А
• А
• А
• А
Regular version of the site
Master 2020/2021

Theory of Computation

Type: Elective course (Data Science)
Area of studies: Applied Mathematics and Informatics
When: 1 year, 1, 2 module
Mode of studies: offline
Master’s programme: Data Science
Language: English
ECTS credits: 5

Course Syllabus

Abstract

This course teaches a mathematical theory that helps to invent better algorithms. With “better” we mean that the algorithms use fewer resources such as time or memory. We also consider parallel computation, distributed systems and learning problems. In these settings we might also optimize other types of resources. For example, in distributed systems we might want to minimize the amount of communication. We focuss on worst case guarantees. A large part of our time is devoted to the study of what is not possible. In other words, we study fundamental barriers for the existence of programs that use fewer resources than a given bound.

Learning Objectives

• understand the concepts of the complexity classes P, NP, coNP, #P, EXP, NEXP, L, NL, PSPACE, EXPSPACE, BPP, RP
• be able to critically analyse resources used by a program (and optimize them at a high level)
• be able to recognize intractable problems and categorize their difficulty
• have deeper understanding and trained problem solving skills of known materials in: algebra, probability theory, discrete math, algorithms

Expected Learning Outcomes

• To know the complexity classes P, NP, coNP, #P, EXP, NEXP, L, NL, PSPACE, EXPSPACE, BPP, RP; relations among these classes (including separations through the hierarchy theorems); famous open problems
• To know problems that are complete for NP and PSPACE
• To know algorithms for prime testing and cryptography
• To know several classes in communication complexity
• To know circuit complexity, the classes NC_k and AC_k, and P-completeness

Course Contents

• Complexity classes P and NP, reductions, NP-completeness and hierarchy theorems
In this topic many fundamental concepts of the course are introduced. We focus mainly on decision problems of sets of bitstrings. For a fixed set, we consider the problem of deciding whether a string belongs to the set.
• L, NL, PSPACE, EXPSPACE, and PSPACE-completeness of some games
We define space complexity classes and show that a large group of games are in the class PSPACE. Space is a much stronger resource than time because it can be reused. We prove the space analogue of the P=NP problem, which is called Savitch theorem: PSPACE = NPSPACE. Again we define PSPACE completeness. The decision problem TQBF considers a fully quantified Boolean formula and asks whether this formula is true. We show that this problem is PSPACE-complete. Then we show that finding winning strategies in games corresponds to PSPACE complete problems.
• Oracle computations and oracles the P vs NP problem relative to specific oracles
We define computation for devices that have access to a device that stores or solves the decision problem for another language.
• Randomized computation and prime testing
The complexity class BPP corresponds to sets that are decidable by a polynomial time algorithm that uses randomness and for each input gives the correct answer with probability 1/3. We show that changing the value 1/3 to any other positive number smaller than ½ does not change the definition.
• Communication complexity, property testing, PCP-theorems and inapproximability of NP-hard problems
Imagine Alice holds a string x and Bob holds a string y of equal length n. They want to figure out whether x = y. We show that in every communication protocol for this problem, there exist x and y for which Alice and Bob communicate at least n bits. The field of communication complexity gives many more results about such problems. We consider also non-deterministic classes.
• Cryptography
We define one-way function and RSA cryptography.
• Circuit complexity and parallel algorithms
In computational complexity, there are several classes that represent problems for which highly efficient parallel algorithms exist. They are given by NC1 , NC2 , … and AC1 , AC2 , … Famous problems in this class are exponentiation and multiplication of matrices. If time permits, we study a few more problems. Finally we study problems that are P-complete, i.e., for which it seems currently unlikely that efficient parallel algorithms will be found.

Assessment Elements

• Homework
• Colloquium
Oral discussion of the theoretical material.
• Exam

Interim Assessment

• Interim assessment (2 module)
0.35 * Colloquium + 0.3 * Exam + 0.35 * Homework

Recommended Core Bibliography

• Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712