Магистратура
2020/2021
Теория вычислений
Статус:
Курс по выбору (Науки о данных)
Направление:
01.04.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Прогр. обучения:
Науки о данных
Язык:
английский
Кредиты:
5
Контактные часы:
56
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 theoremsIn 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 gamesWe 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 oraclesWe define computation for devices that have access to a device that stores or solves the decision problem for another language.
- Randomized computation and prime testingThe 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 problemsImagine 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.
- CryptographyWe define one-way function and RSA cryptography.
- Circuit complexity and parallel algorithmsIn 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.
Bibliography
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
Recommended Additional Bibliography
- Du, D., & Ko, K.-I. (2014). Theory of Computational Complexity (Vol. Second edition). Hoboken, New Jersey: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=784130
- Katz, J., & Lindell, Y. (2014). Introduction to Modern Cryptography (Vol. Second edition). Boca Raton, FL: Chapman and Hall/CRC. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=nlebk&AN=1766746
- Roughgarden, T. (2015). Communication Complexity (for Algorithm Designers). Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1509.06257