SubjectsSubjects(version: 928)
Course, academic year 2022/2023
   Login via CAS
Complexity - NTIN063
Title: Složitost
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: summer
E-Credits: 4
Hours per week, examination: summer s.:2/1, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: prof. RNDr. Ondřej Čepek, Ph.D.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Theoretical Computer Science
Co-requisite : NTIN062
Is co-requisite for: NTIN081
Is incompatible with: NTIX063
Is interchangeable with: NTIX063
Annotation -
Last update: T_KTI (28.04.2015)
This course extends the basic course on computational complexity. It introduces the students to the concepts of polynomial hierarchy classes, probabilistic computation, oracle computation, non-uniform computational models and the PCP theorem.
Aim of the course -
Last update: prof. RNDr. Ondřej Čepek, Ph.D. (26.09.2020)

The aim is to learn more advanced topics from the complexity theory, complexity classes, their properties and mutual relations.

Course completion requirements -
Last update: RNDr. Petr Kučera, Ph.D. (30.04.2020)

Credit is given for solving enough homework assignments. The lecture is finished with an oral exam. Depending on the situation, it is possible that the exam can proceed remotely.

Literature -
Last update: T_KTI (28.04.2015)

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

Balcázar, Díaz, Gabarró : Structural Complexity I, Springer Verlag 1988

Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press 2008

Syllabus -
Last update: T_KTI (28.04.2015)

1) Oracle Turing machines.

2) Polynomial hierarchy (definitions based on oracles and on alternating quantifiers, proof of their equivalence)

3) Quantified boolean formulas QBF and their completenes for PSPACE and Σi.

4) Nondeterministic hierarchy theorems.

5) Log-space reducibility, P-completeness and its consequences.

6) Szelepcsenyi-Immerman theorem, NL=coNL.

7) Non-uniform computational models - advice functions, boolean circuits, classes NC and P/poly, functions with

maximum circuit size.

8) Probabilistic algorithms - classes RP, coRP, ZPP, and BPP.

9) Error reduction in BPP, BPP is in P/poly, BPP is in Σ2.

10) NP-completeness of UNIQUE-SAT (probabilistic reduction)

11) PCP theorem (without proof) and its applications in inaproximability.

Registration requirements - Czech
Last update: RNDr. Jan Hric (07.06.2019)


Charles University | Information system of Charles University |