Computational complexity 1000-218bZO
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.
Type of course
Course coordinators
Learning outcomes
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.
Assessment criteria
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.
Bibliography
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
Notes
|
Term 2024Z:
None |
Term 2025Z:
None |
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: