Computational complexity

obligatory courses

Complexity theory is complementary to algorithmics. While algorithmics provides efficient solutions of computational problems, complexity theory explains why some problems are too hard to be solved by good algorithms, and classifies problems according to their difficulty. It also evaluates various features that may enhance the traditional model of computation, like randomness, parallelism, interaction, or quantum effects.

1. Coding objects by words, decision and function problems.

2. Basic models of computation: Turing machine, RAM, logical circuits.

3. Time and space complexity, the concept of complexity class.

4. Polynomial time complexity and its practical importance, non-trivial examples.

5. The class NP, P=/=NP conjecture, the concept of reduction, NP-complete problems, function problems in NP.

6. Constructive approach to difficult problems: approximation algorithms, fixed parameter tractability, average polynomial complexity.

7. Randomized computations, probabilistic complexity classes, pseudo-random generators and the issue of derandomization.

8. The class PSPACE and interactive models of computations: alternating machines, interactive proofs, games against Nature.

9. One-way functions and the use of computational difficulty on cryptography, zero-knowledge proofs.

10. How to prove hardness: diagonal method, hierarchy theorems. Limitation of this method for proving P=/=NP conjecture.

11. Fine grained complexity, parameterized complexity, exponential time hypothesis.

C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

A.Arora, B.Barak Computational Complexity: A Modern Approach, Cambridge University Press, 2009 http://www.cs.princeton.edu/theory/complexity/

M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.

Oded Goldreich Complexity Theory - Material http://www.wisdom.weizmann.ac.il/~oded/cc.html

Knowledge.

1. A student has in-depth knowledge in the fields of mathematics necessary to study computer science (complexity theory) [K_W01].

2. A student understands well the role and importance of the construction of mathematical reasoning [K_W02].

3. A student understands successive levels of generality: complexity of an algorithm, complexity of a problem, a class of complexity.

4. A student understands the notions of time and memory complexity in the sequential model of a Turing machine and the equivalents of these notions in the logical circuit model.

5. A student understands the non-uniform and probabilistic computation model and knows the relationship between them.

6. A student knows examples of problems in the basic complexity classes: NC, L, NL, P, NP, PSPACE, P/poly, BPP.

7. A student understands the notions of reductions between problems and the notion of NP-completeness.

8. A student knows the quality criteria of approximation algorithms.

9. A student knows examples of a positive use of computational complexity in cryptography.

Skills.

1. A student has the ability to construct mathematical reasoning [K_U01].

2. A student can express computational problems in the language of mathematics [K_U02].

3. A student designs algorithms in basic computational models: Turing machines, logical circuits [K_U04].

4. A student identifies membership and hardness of computational problems with respect to important complexity classes: NC, P, NP, PSPACE, using their different characterizations [K_U05].

5. A student has language skills in the field of computer science in accordance with the requirements set for the B2+ level of the Common European Framework of Reference for Languages, in particular: identifies the main and side topics of lectures, talks, academic debates, discussions, reads with understanding and critically analyzes academic texts, takes part in a discussion or a scientific debate, verbally summarizes the information, research results, opinions and arguments of an author contained in a scientific text [K_U14].

6. A student can, in natural cases, recognize computationally difficult problems.

7. A student can, in typical cases, classify a given problem into one of the main complexity classes.

8. A student can, in typical cases, design an approximation or a randomized algorithm for a problem for which a deterministic solution is unknown.

Competence.

1. A student understands the importance of computational complexity as a barrier for standard IT techniques, forcing to find other techniques.

2. A student understands the usefulness of the information on computational complexity of practical problems.

3. A student understands the importance of hypotheses of the complexity theory among the priority problems of modern mathematics.

Five homeworks and a written exam. You need at least 40% from the homeworks to be admitted to the first exam. You need at least 35% from the exam and 50% of the combined points from homeworks and the exam to pass; the grade depends on the combined points from homeworks and the exam. In the first exam, the points are combined as (60% homeworks + 40% exam), in the second exam as maximum of as in the first exam and (40% homeworks + 60% exam).

All solutions should be written in English.

In the case of completing the course by a doctoral student, the student will read a selected recent research article and a chat with a lecturer about the article will be a part of the exam.