• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Theory of Computation

2020/2021
Academic Year
ENG
Instruction in English
5
ECTS credits
Course type:
Elective course
When:
3 year, 1, 2 module

Instructors


Obiedkov, Sergei

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

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

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

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

Assessment Elements

  • non-blocking Homework
  • non-blocking Colloquium
    Oral discussion of the theoretical material.
  • non-blocking Exam
Interim Assessment

Interim Assessment

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

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