Course for international guest/part time students
- Faculty
- Faculty of Science
- Organization
- TTK Department of Computer Science
- Code
- bonyel1u0um20gm
- Title
- Complexity theory (p)
- Usual semester
- Autumn
- Published semester
- 2026/27/1
- ECTS
- 3
- Language
- hu
- Learning outcomes
- Knowledge: getting familiar with the main notions of complexity theory Ability: to apply the learned algorithms for solving complex problems Attitude: the need to deepen the applied mathematical knowledge, to gain new applied mathematical skills, to develop competencies. Aspiration to apply the mathematical knowledge for a wide range of problems Autonomy and Responsibility: based on the gained knowledge within complexity theory, the students are able to decide which tools are the most suitable to solve applied problems
- Course content
- Communication complexity. Decision trees, Ben-Or theorem. Hierarchy theorems, Sawitch theorem, oracles, polynomial hierarchy. The class PSPACE, complete languages. Randomised complexity classes. Pseudo-random generators. Interactive protocols. Shamir theorem: IP=PSPACE. PCP theorem. Lower bouds over Boolean networks. Parallel algorithms for arithmetical problems, orderings and linear algebraic problems. Parallel algorithms for networks of low degree. Kolmogorov-complexity.
- Assessment method
- term grade