I017 Structural Complexity

Faculty of Informatics
Spring 2001
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Timetable
Tue 8:00–9:50 B411
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
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.
  • Kolmogorov complexity. Lower bounds proof technique based on Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • Complexity theory retrospective. Edited by Lane A. Hemaspaandra - Alan L. Selman. New York: Springer-Verlag, 1997, xi, 339. ISBN 0387949739. info
  • GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. info
  • BALCÁZAR, José Luis, Josep DÍAZ and Joaquim GABARRÓ. Structural complexity I. Berlín: Springer-Verlag, 1995, xiii, 208. ISBN 3-540-58384-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Assessment methods (in Czech)
Během semestru studenti samostatně řeší zadané problémy. Řešení jsou základem pro určení závěrečného hodnocení.
Language of instruction
Czech
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i017.html
The course is also listed under the following terms Autumn 1995, Autumn 1996, Autumn 1997, Autumn 1998, Spring 2000, Spring 2002, Spring 2003.
  • Enrolment Statistics (Spring 2001, recent)
  • Permalink: https://is.muni.cz/course/fi/spring2001/I017