IIC3242 - Complejidad Computacional

Semestre 1 - 2019

The course is given in English, so it's title is really Computational Complexity.

This page will include the course slides (the most recent version) and homeworks. You can check previous year's homeworks via the links below.

Course program

Slides

I would like to thank Marcelo Arenas for giving me a preliminary version of these slides. I built on top of the materials he used when teaching the course.

Topic 0: Course overview

Topic 1: Turing machines

Topic 2: Time complexity

Topic 3: Space complexity

Topic 4: Relationships between complexity classes

Topic 5: Polynomial hierarchy

Topic 6: Circuit complexity

Topic 7: Probabilistic complexity classes

Homework assignments

2018 homeworks

2017 homeworks

2016 homeworks

References

Michael Sipser. Introduction to the Theory of Computation. Second Edition. Thompson Course Technology, 2006.
Christos Papadimitriou. Computational Complexity. Addison Wesley, 1994.
Sanjeev Arora and Boaz Barak. Computational Complexity. A modern approach. Cambridge University Press, 2009.