Complexity Theory

Přednášející:

Luděk Kučera (gar.)

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Students will learn about the fundamental classes of problems in the complexity theory and different models of algoritms and about implications of the theory concerning practical (un)solvability of difficult problems.

Požadavky:

Osnova přednášek:

1. Models of computation.\r

2. Algorithmic undecidability.\r

3. Nondeterminism, the class NP, the existence of an NP-complete problem.\r

4. NP-complete problems.\r

5. Problem P=NP, relativization, classes coNP and NP intersection coNP.\r

6. The class PSPACE, Savitch theorem, hierarchy in PSPACE.\r

7. PSPACE-complete problem (quantified formulae and games), complete problem for the hierarchy classes.\r

8. Circuit and algebraic complexity.\r

9. Randomized algorithms, complexity classes of randomized algorithms (classes BPP, ZP, RP).\r

10. One-way functions, pseudorandom sequences, discrete logarithm, cryptography.\r

11. Interactive proofs, probabilistically verifiable proofs, expanders, gap problem, PCP theorem, non-aproximability of 3SAT.\r

Osnova cvičení:

1. Mutual simulations of computational models.

2. [2] NP-complete problems and their reductions.

3. Particular problems in coNP and NP intersection coNP.

4. [2] Complete problems for PSPACE and different classes of the hierarchy in PSPACE.

5. [2] Examples of circuits for different simple problems, bounded fan-in.

6. [3] Examples of different Monte-Carlo and Las Vegas algorithms.

7. Examples of pseudorandom sequences ans simple facts about their (non-)predictability.

8. Amplification of a success probability, examples of randomized algorithms.

9. Expanders and random walks, Markov chains and their mixing.

Cíle studia:

Provide a theoretical background for deciding whether a given problem is, according to our present knowledge, solvable and what kind of computational methods could be used.

Studijní materiály:

1. Arora, S., Barak, B. ''Computational Complexity: A Modern Approach''. Cambridge University Press, 2009. ISBN 0521424267.

2. Goldreich, O. ''Computational Complexity: A Conceptual Perspective''. Cambridge University Press, 2008. ISBN 052188473X.

3. Motwani, R., Raghavan, P. ''Randomized Algorithms''. Cambridge University Press, 1995. ISBN 0521474655.

Poznámka:

Rozsah=prednasky+proseminare+cviceni3p+1c, Prednasejici: prof. RNDr. Luděk Kučera DrSc.

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• System Programming, in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět oboru)
• Computer Science, Presented in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět oboru)
• Master Informatics, Presented in English - Version for Students who Enrolled in 2010 (VO)
• Master Informatics, Presented in English - Version for Students who Enrolled in 2011 (VO)
• Master Informatics, Presented in English - Version for Students who Enrolled in 2012 (VO)
• System Programming, Presented in English - Version for Students who Enrolled in 2012 (povinný předmět oboru)
• Computer Science, Presented in English - Version for Students who Enrolled in 2012 (povinný předmět oboru)