FI:I017 Structural Complexity - Course Information
I017 Structural Complexity
Faculty of InformaticsAutumn 1998
- Extent and Intensity
- 2/0. 2 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
- Teacher(s)
- prof. RNDr. Ivana Černá, CSc. (lecturer)
- Guaranteed by
- Contact Person: prof. RNDr. Ivana Černá, CSc.
- Prerequisites
- I012 Complexity
The course expands on I012. - Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Informatics (programme FI, B-IN)
- Informatics (programme FI, M-IN)
- Upper Secondary School Teacher Training in Informatics (programme FI, M-IN)
- Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
- Information Technology (programme FI, B-IN)
- Syllabus
- More on complexity classes; their structure and properties. Comparison of various complexity measures.
- Lower bound techniques.
- The polynomial hierarchy.
- Computation that counts.
- Alternation and games. Games against nature and interactive protocols.
- Interactive proof systems. Zero-knowledge proofs and transparent proofs. Probabilistic checking of proofs. Interactive program validation.
- Language of instruction
- Czech
- Further Comments
- The course is taught annually.
The course is taught: every week. - Teacher's information
- http://www.fi.muni.cz/usr/cerna/i017.html
- Enrolment Statistics (Autumn 1998, recent)
- Permalink: https://is.muni.cz/course/fi/autumn1998/I017