Computability and Complexity
Objectives
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
Code
8415
Credits
6.0
Responsible teacher
Isabel Maria Oitavem Fonseca da Rocha Kahle
Hours
Weekly - 4
Total - 48
Teaching language
Português
Prerequisites
---
Bibliography
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.