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. Other approaches to proving hardness: information complexity by Kolmogorov, randomized restrictions in Boolean circuits, communication complexity. Successes and limitations.

12. Physical limits of computability, the concept of quantum computing.

The last three lectures should contain a more focused material selected by the lecturer. The selection may be connected with topics of the main thread of the course, but it may also concern different issues. Potential topics include:

- complexity vs cryptography,

- complexity in databases,

- correction codes,

- constraint satisfaction problems,

- interactive proofs,

- games against Nature,

- PCP,

- quantum complexity,

- parameterized complexity,

- models of communication complexity.

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.

The final grade consists of: homeworks (up to 40%), mid-term results (up to 25%), and results of the final written exam. Furthermore, after every lecture we will publish a short simple quiz in moodle; you need to score over 75% points from all quizes to be admitted to the exam in the first exam session. In the second term, points earned for the mid-term do not count towards the final grade (but points from homeworks do count). 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.