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.
Isabel Maria Oitavem Fonseca da Rocha Kahle
Weekly - 4
Total - 48
Main book: Computability and Complexity Theory, Steven Homer and Alan L. Selman, Springer.
- 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.
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.
1- Introduction to computability;
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: