Computability and Complexity


Developing knowledge concerning models of computation, and classes of complexity like P, NP, Pspace,... Developing skills that allow to understand not only the main results involving these classes of complexity, but also several of the open problems in the area.

General characterization





Responsible teacher

Isabel Maria Oitavem Fonseca da Rocha Kahle


Weekly - 4

Total - 48

Teaching language





Main book:  Computability and Complexity Theory, Steven Homer and Alan L. Selman, Springer.

Other books:

- Structural Complexity, vol. I and II, Balcázar, Días and Gabarró, Springer.

- Mathematical Logic, Part II, Cori and Lascar, Oxford.

- Computability, Klaus Weihrauch, Springer.

- Handbook of Logic and Computer Science, Gabbay and Maibaum (ed.), Oxford University Press.

- A Programming approach to computability, Kfoury, Moll and Arbib, Springer.

- Computers and Intractability. A Guide to the Theory of NP-Completeness, Garey and Johnson, W.H.Freeman and Co., San Francisco.

Teaching method

Available soon

Evaluation method

The student must attend to 2/3 of the given lectures.


Evaluation is based on one project per student (presentation, discussion and report) and one test. Each seminar contributs with 16 points to the final grade, and the project contributs with 4 points.

Grades greater or equal than 10 points lead to approval.

Whenever the grade is more or equal than 18 points, an extra examination might be required. If the student declines it, the final grade of 17 points will be given.

Subject matter

1- Introduction to computability;

2- Undecidability;

3- Introduction to complexity theory;

4- Basic results of complexity theory;

5- Nondeterminism and NP-completeness;

6- Relative complexity.


Programs where the course is taught: