IA012 Complexity

Faculty of Informatics
Spring 2006
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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
Thu 10:00–11:50 B410
Prerequisites (in Czech)
! I017 Structural Complexity
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost
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
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory clasiffies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Assessment methods (in Czech)
V průběhu semsestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.
  • Enrolment Statistics (Spring 2006, recent)
  • Permalink: https://is.muni.cz/course/fi/spring2006/IA012